Задача №1950. Накопительная скидка
В некотором интернет - магазине действует N накопительных скидок. Когда сумма, уплаченная каким-то клиентом за его предыдущие заказы превысит x1, начинает действовать скидка a1 (это означает что за последующие покупки клиент платит на a1 процентов меньше). Затем, когда суммарная стоимость покупок превысит x2 начинает действовать скидка a2. И так далее. Когда суммарная стоимость покупок превысит xn, то начинает действовать скидка an. Известно, что a1<a2<…<an.
Покупатель хочет купить K товаров в определенном порядке. Рассчитайте, какую сумму денег потратит покупатель (считается, что каждый товар он будет оформлять отдельным заказом, поэтому к моменту следующей покупки на нее будет распространяться самая большая возможная скидка.
Сначала вводится число N (натуральное, не превышает 10) – общее количество скидок. Затем вводится N пар чисел: величина скидки ai (натуральное, не превышает 100) и сумма, которую надо превысить чтобы получить такую скидку xi (натуральное, не превышает 100000). Далее вводится число K – количество товаров, которые хочет приобрести покупатель (натуральное, не более 100). Затем следует K чисел – цена каждого товара (натуральное, не более 1000). Гарантируется, что каждая следующая скидка дается после большей суммы, чем предыдущая, также гарантируется что величина каждой следующей скидки больше предыдущей. Гарантируется, что все цены в интернет-магазине кратны 100.
Выведите единственное число – сколько денег потратит покупатель при заданном порядке покупок.
Пример:
| Исходные данные | Результат |
| 2 2 10 4 100 2 100 100 | 198 (обратите внимание, что скидка начисляется только после превышения суммы, поэтому после первой покупки скидка равна не 4, а 2%) |
| 3 2 10 4 20 8 30 1 1000 | 1000 (скидка начисляется только после совершения покупки) |