SOC

Submit solution
Points: 100
Time limit: 1.0s
Memory limit: 493M
Problem type

Có \(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ẻ.

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[1], t[2], …, t[m]; (t[i]<=100)\);

  • Dòng thứ ba chứa \(m\) số nguyên \(p[1], p[2], …, p[m]; (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.

Sample Input

3 2 5
5 1 2
1 2 1

Sample Output

4

Comments