C. Geometry Horse
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вася играет в Geometry Horse.

Цель игры — уничтожить геометрические фигуры, находящиеся в игровом мире. За уничтожение фигуры начисляется определенное число очков в зависимости от типа фигуры и текущего множителя.

В данной игре имеется n видов геометрических фигур, для каждого вида известно количество фигур данного вида ki и стоимость одной фигуры данного вида ci. За уничтожение одной фигуры вида i игроку начисляется ci·f очков, где f — текущий множитель. Множитель может принимать целые значения от 1 до t + 1 включительно. Изначально множитель равен 1. После уничтожения pi (1 ≤ i ≤ t) фигур множитель становится равен i + 1, таким образом, фигура, уничтоженная по счету ровно (pi + 1)-ой, учитывается уже со множителем i + 1.

Ваша задача — определить, какое наибольшее число очков может набрать Вася, уничтожив все фигуры. Учтите, что Вася настолько силен, что может уничтожать фигуры в любом выбранном им порядке.

Входные данные

Первая строка содержит единственное целое число n (1 ≤ n ≤ 100) — количество типов геометрических фигур.

В каждой из следующих n строк содержатся два целых числа, записанных через пробел, ki и ci (1 ≤ ki ≤ 109, 0 ≤ ci ≤ 1000) — количество фигур i-го вида и стоимость одной фигуры i-го вида, соответственно.

В следующей строке содержится единственное целое число t (1 ≤ t ≤ 100) — ограничение на текущий множитель.

В следующей строке содержатся t целых чисел, записанных через пробел, pi (1 ≤ p1 < p2 < ... < pt ≤ 1012) — числа описывающие изменения множителя.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите единственное число — наибольшее количество очков, которое может набрать Вася.

Примеры
Входные данные
1
5 10
2
3 6
Выходные данные
70
Входные данные
2
3 8
5 10
1
20
Выходные данные
74
Примечание

В первом примере Вася сначала уничтожит три фигуры и получит 3·1·10 = 30 очков. Затем множитель станет равным 2 и Вася, уничтожив оставшиеся две фигуры, получит еще 2·2·10 = 40 очков. Всего Вася получит 70 очков.

Во втором примере все 8 фигур будут уничтожены с коэффициентом 1, поэтому всего Вася наберет (3·8 + 5·10)·1 = 74 очка.