I. Параллельные курсы
Задачу добавил: alef
Успешно сдано решений: 9
Министры царя Пантелеймона с большим энтузиазмом отнеслись и к составлению курсов, и к тому, чтобы сделать большинство этих курсов обязательными для жителей царства. Только министр промышленности Силантий опять в сомнениях: ежели каждого жителя обязать все курсы проходить, на это может и не один год потребоваться.
Министр науки Фалалей возразил, что для каждого курса есть оценки, которые показывают, что пройти курсы можно очень быстро. Да и проходить можно, например, два курса параллельно.
Имеется два обучающих курса, материал в которых разбит на блоки. Первый курс состоит из $$$n$$$ блоков, второй курс — из $$$m$$$ блоков. Для каждого блока известна его длительность — $$$f_j$$$ дней для первого и $$$s_i$$$ для второго. Также для каждого блока известна его сложность — $$$p_j$$$ для первого курса и $$$q_i$$$ для второго курса соответственно.
Менять порядок блоков в курсе или изучать блок быстрее, чем предусмотрели разработчики курса, слушатель не может. Если слушатель начал изучать блок $$$\#k$$$ (какого-либо курса), то в течение $$$f_k$$$ дней, если это был первый курс, или же в течение $$$s_k$$$ дней, если это был второй курс, ему будет выдаваться материал этого блока. Приостановить изучение блока или позже изучить его повторно слушатель не сможет; но он может, завершив изучение некоторого блока сделать перерыв любой длительности перед тем, как приступит к изучению следующего блока.
Слушатель может изучать в один день материал какого-либо блока первого курса и материал какого-либо блока второго курса — но при условии, что суммарная сложность этих блоков не превосходит величину $$$R$$$ (гарантируется, что сложность любого блока любого курса не превосходит эту величину).
Слушатель хочет изучить оба курса как можно быстрее. Если слушатель завершает изучение курсов не одновременно, то он считается изучившим оба курса тогда, когда завершит изучение последнего из них.
Ваша задача — определить минимальное время, которое требуется слушателю, чтобы изучить оба курса.
В первой строке содержится целое число $$$R$$$ $$$(1 \le R \le 10^9)$$$ — максимально допустимая суммарная сложность блоков, изучаемых в один день.
Во второй строке содержится целое число $$$n$$$ $$$(1 \le n \le 500)$$$ — количество блоков в первом курсе.
В третьей строке содержится $$$n$$$ целых числе $$$f_1, f_2, \ldots, f_n$$$ $$$(1 \le f_j \le 10^6, \, j = 1, 2, \ldots, n)$$$ — длительности блоков первого курса.
В четвёртой строке содержится $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ $$$(1 \le p_j \le R, \, j = 1, 2, \ldots, n)$$$ — сложности блоков первого курса.
В пятой строке содержится целое число $$$m$$$ $$$(1 \le m \le 500)$$$ — количество блоков во втором курсе.
В шестой строке содержится $$$m$$$ целых числе $$$s_1, s_2, \ldots, s_m$$$ $$$(1 \le s_i \le 10^6, \, i = 1, 2, \ldots, m)$$$ — длительности блоков второго курса.
В седьмой строке содержится $$$m$$$ целых чисел $$$q_1, q_2, \ldots, q_m$$$ $$$(1 \le q_i \le R, \, i = 1, 2, \ldots, m)$$$ — сложности блоков второго курса.
Выведите целое число — минимальное время, которое потребуется слушателю, чтобы изучить оба курса.
10 5 3 8 5 4 2 2 7 3 6 4 4 4 6 3 7 4 5 5 3
28
Поясним приведённый пример.
Будем для краткости обозначать блок $$$Y$$$ курса $$$X$$$ как $$$X.Y$$$.
Слушатель начнёт изучать первые блоки обоих курсов одновременно: суммарная сложность составляет $$$2 + 4 = 6$$$, что меньше разрешённой сложности $$$10$$$. Освоение блока $$$1.1$$$ слушатель завершит в день 3, а в день 4 он будет изучать только блок $$$2.1$$$. Сложность блока $$$2.1$$$ составляет 4, а сложность блока $$$1.2$$$, который слушатель мог бы изучить сразу после блока $$$1.1$$$, составляет 7, поэтому изучать их параллельно нельзя, поскольку $$$7 + 4 > 10$$$.
В день 4 блок $$$2.1$$$ будет завершён, но поскольку суммарная сложность блоков $$$1.2$$$ и $$$2.2$$$ составляет $$$7 + 5 = 12 > 10$$$, слушателю придётся выбрать для изучения либо второй блок первого курса, либо второй блок второго курса.
Для достижения оптимального результата слушателю следует выбрать блок $$$1.2$$$. На его изучение он потратит $$$8$$$ дней и завершит его изучение в день 12.
Суммарная сложность блоков $$$1.3$$$ и $$$2.2$$$ составляет $$$3 + 5 = 8 \le 10$$$, так что их слушатель может изучать одновременно. Блок $$$1.3$$$ он завершит изучать через 5 дней, однако начать изучение блока $$$1.4$$$ сразу после этого блока слушатель не сможет: сложность этого блока составляет $$$6$$$, а $$$6 + 5 = 11 > 10$$$. Поэтому сначала ему придётся завершить изучение блока $$$2.2$$$, и это произойдёт в день 18.
Теперь слушатель снова оказывается перед выбором: суммарная сложность блоков $$$1.4$$$ и $$$2.3$$$ составляет $$$6 + 5 = 11 > 10$$$, что означает невозможность изучать их одновременно. Оптимальная стратегия состоит в том, чтобы изучить сначала блок $$$2.3$$$, потратив на это 3 дня и завершив изучение этого блока в день 21.
Блоки $$$1.4$$$ и $$$2.4$$$ имеют суммарную сложность $$$6 + 3 = 9 \le 10$$$, и слушатель начнёт изучать их одновременно. Длительность блока $$$1.4$$$ — 4 дня, а блока $$$2.4$$$ — 7 дней. Впрочем, спустя 4 дня, завершив изучение блока $$$1.4$$$, слушатель сможет приступить к изучению блока $$$1.5$$$: $$$4 + 3 = 7 \le 10$$$. Длительность блока $$$1.4$$$ — 2 дня, так что и этот блок будет завершён ещё до окончания изучения блока $$$2.4$$$. Наконец, по прошествии 7 дней блок $$$2.4$$$ также будет изучен, и это произойдёт на 28 день.