#259. SQUIRR2 - Sóc và hạt giẻ

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

N chú sóc đang đứng chờ dưới gốc của M cây hạt dẻ. Cây hạt dẻ thứ i sẽ bắt đầu rụng quả đầu tiên sau T_i giây nữa, và cứ sau P_i giây lại rụng thêm một quả. Sóc mẹ muốn các cậu con trai của mình mang về tổ không ít hơn k quả hạt dẻ để chuẩn bị tránh cơn sóng thần dữ dội đến từ biển Đông xa xôi, nhưng cũng phải thật nhanh chóng trước khi cơn sóng thần kịp ập đến chứ chẳng thể nhởn nhơ! Vậy nên các chú sóc đang bàn nhau xem nên đứng ở những gốc cây nào để có thể hứng đủ số quả cần thiết trong thời gian nhanh nhất. Thời gian để các chú sóc đi về vị trí cần đứng coi như không đáng kể, các chú sóc cũng không di chuyển sang gốc cây nào khác trong lúc đang hứng hạt dẻ.

Yêu cầu: Hãy tính thời gian sớm nhất (sau bao nhiêu giây nữa) các chú sóc có thể hứng đủ số quả cần thiết.

Dữ liệu vào:

  • Dòng đầu chứa ba số nguyên dương M, N, K\ (0 < M,N≤50000; 0< k≤10^9) ;
  • Dòng thứ hai chứa M số nguyên T_i\ (0< T_i≤100) ;
  • Dòng thứ ba chứa M số nguyên P_i\ (0< P_i≤100) .

Dữ liệu ra:

  • Ghi ra trên một dòng duy nhất một số nguyên là thời gian sớm nhất tìm được.

Ví dụ:

Dữ liệu vào:
3 2 5
5 1 2
1 2 1
Dữ liệu ra:
4

Giải thích: Hai chú sóc đứng ở gốc cây 2 3 .