Задача №111893. Бюджет
Всем известно, что основной целью любого крупного правительственного проекта во Флатландии является освоение бюджетных средств (разумеется, по назначению). В настоящее время во Флатландии ведется работа над m национальным проектами, i-й проект может освоить \(s_i\) миллионов Флатландских тугриков в день.
Правительство Флатландии планирует выделить \(n\) грантов для финансирования проектов, каждый по p миллионов Флатландских тугриков. Деньги i-го из грантов будут доступны для освоения, начиная с дня \(r_i\). Когда очередной грант становится доступен для освоения, его можно отдать некоторому проекту. Этот проект осваивает деньги гранта в течение \(\lceil\frac{p}{s_i}\rceil\) дней. Проект не может одновременно осваивать деньги нескольких грантов.
Премьер-министр Флатландии господин Тупиков хочет выяснить, за какое время удастся освоить все деньги, выделенные в рамках грантов. Помогите ему выяснить самый ранний день, когда можно полностью освоить все деньги грантов.
Первая строка входного файла "budget.in" содержит числа m, n и p (1 ≤ m ≤ 100, 1 ≤ n ≤ 100, 1 ≤ p ≤ \(10^9\)). Вторая строка содержит m целых чисел: \(s_1\), \(s_2\), . . . , \(s_m\) (1 ≤ \(s_i\) ≤ \(10^9\)). Третья строка содержит n целых чисел: \(r_1\),\(r_2\),...,\(r_n\) (1 ≤ ri ≤ \(10^9\)).
Первая строка выходного файла "budget.out" должна содержать одно целое число — минимальный день, к которому можно полностью освоить все деньги грантов.
Одна из возможных оптимальных схем освоения устроена следующим образом: грант 1 отдается первому проекту, который осваивает его в течение 11 дней. Остальные гранты отдаются второму проекту, грант 2 осваивается в течение дней 3–7, грант 3 в течение дней 8–12 и грант 4 в течение дней 13–17. Заметим, что грант 4 появляется в день 12, но назначается только в день 13.
2 4 22 2 5 1 3 8 12
17