Дмитрий и Анна — муж и жена. Как это нередко бывает, они являются гражданами разных стран. В каждой из этих стран применяется прогрессивная система налогообложения.
А именно, в стране Дмитрия система налогообложения на доход физических лиц устроена следующим образом:
- сумма дохода, не превосходящая $$$a_1$$$, облагается налогом в размере $$$p_1$$$%;
- часть дохода, превышающая $$$a_1$$$, до общего дохода $$$a_2$$$, облагается налогом в размере $$$p_2$$$%;
- часть дохода, превышающая $$$a_2$$$, до общего дохода $$$a_3$$$, облагается налогом в размере $$$p_3$$$%, и так далее,
- наконец, часть дохода, превышающая $$$a_n$$$, облагается налогом в размере $$$p_{n+1}$$$%.
Например, если $$$n=3$$$, $$$a_1=100$$$, $$$a_2=300$$$, $$$a_3=1000$$$, и $$$p_1=10$$$, $$$p_2=12$$$, $$$p_3=14$$$, $$$p_4=16$$$, и общий доход составляет $$$1234$$$, то этот доход делится на следующие части: сумма $$$100$$$ облагается налогом в размере $$$10$$$%, сумма $$$200$$$ (т. е. от $$$100$$$ до $$$300$$$) облагается налогом $$$12$$$%, сумма $$$700$$$ (т. е. от $$$300$$$ до $$$1000$$$) — налогом $$$14$$$%, и оставшаяся сумма $$$234$$$ (от $$$1000$$$ до $$$1234$$$) — налогом $$$16$$$%. Итоговая сумма налога равна $$$100\cdot 0.10+200\cdot 0.12+700\cdot 0.14+234\cdot 0.16=169.44$$$.
Аналогично, если общий доход составляет $$$50$$$, то налог будет равен $$$50\cdot 0.10=5$$$, а если общий доход составляет ровно $$$300$$$, то налог будет равен $$$100\cdot 0.10+200\cdot 0.12=34$$$.
В стране Анны действует аналогичная система, но с другими параметрами:
- сумма дохода, не превосходящая $$$b_1$$$, облагается налогом в размере $$$q_1$$$%;
- часть дохода, превышающая $$$b_1$$$, до общего дохода $$$b_2$$$, облагается налогом в размере $$$q_2$$$%;
- часть дохода, превышающая $$$b_2$$$, до общего дохода $$$b_3$$$, облагается налогом в размере $$$q_3$$$%, и так далее,
- наконец, часть дохода, превышающая $$$b_m$$$, облагается налогом в размере $$$q_{m+1}$$$%.
За прошлый год суммарный доход Дмитрия и Анны равен $$$X$$$. Теперь они должны уплатить налоги с него. Конкретно, Дмитрий может задекларировать некоторую сумму дохода $$$t$$$, и уплатить с него налог согласно налоговому законодательству страны Дмитрия, а Анна тогда задекларирует сумму дохода, равную $$$X-t$$$, и уплатит с нее налог согласно налоговому законодательству страны Анны.
Помогите им задекларировать доход так, чтобы суммарный уплаченный доход был как можно меньше.
Первая строка содержит одно целое число $$$n$$$ — количество «уровней» налогов в стране Дмитрия ($$$0 \leq n \leq 100\,000$$$).
На второй строке находятся $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — пороговые суммы в законодательстве страны Дмитрия ($$$1\leq a_i\leq 10^{16}$$$; гарантируется, что $$$a_i \lt a_{i+1}$$$ для каждого $$$i$$$).
На третьей строке находится $$$n+1$$$ целое число $$$p_1$$$, $$$p_2$$$, ..., $$$p_{n+1}$$$ — ставки налогов в стране Дмитрия ($$$0\leq p_i\leq 100$$$).
Следующие три строки содержат описание налогового законодательства страны Анны в том же формате (на первой из них одно число $$$m$$$, на следующей $$$m$$$ чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$, на следующей $$$m+1$$$ число $$$q_1$$$, $$$q_2$$$, ..., $$$q_{m+1}$$$; ограничения на эти числа аналогичны ограничениям на параметры страны Дмитрия).
На седьмой строке входных данных находится одно целое число $$$X$$$ — суммарный доход Дмитрия и Анны ($$$0\leq X\leq 10^{16}$$$).
Обратите внимание, что $$$n$$$ и/или $$$m$$$ могут быть равны нулю (плоская система налогообложения). В таком случае строки с числами $$$a_i$$$ и/или $$$b_i$$$ будут пустыми.
Выведите одно целое число $$$t$$$ — размер дохода, который должен задекларировать Дмитрий для минимизации суммарного налога. Если существует несколько оптимальных решений, выведите любое из них.
В тестах общей стоимостью не менее 10 баллов дополнительно выполняется $$$n=m=0$$$.
В тестах общей стоимостью не менее 10 баллов дополнительно выполняется $$$n=m=1$$$.
В тестах общей стоимостью не менее 20 баллов дополнительно выполняется $$$p_{i+1}\geq p_i$$$ и $$$q_{i+1}\geq q_i$$$ для всех $$$i$$$ (массивы $$$p$$$ и $$$q$$$ не убывают).
В тестах общей стоимостью не менее 40 баллов дополнительно выполняется $$$n\leq 1000$$$ и $$$m \leq 1000$$$.
1 10 12 17 2 20 40 15 17 20 50
20
1 10 10 20 0 30 50
50
В первом примере Дмитрий платит $$$10\cdot 0.12+10\cdot 0.17=2.9$$$, а Анна платит $$$20\cdot0.15 + 10\cdot 0.17=4.7$$$, суммарный налог получается $$$7.6$$$.
Во втором примере оптимально задекларировать весь доход в стране Дмитрия. В этом случае суммарный налог будет равен $$$50 \cdot 0.2 = 10$$$.
| Name |
|---|