Vasya 扮演几何马。
游戏目标是摧毁游戏世界的几何图形。根据人物类型和当前因子值,破坏每个人物都会获得一定数量的分数。
有 n 种几何图形。对于每种人物类型,类型 ki 的人物数量和人物成本 ci 是已知的。玩家因摧毁一个类型 i 的人物而获得 ci·f 点,其中 f 是当前因素。因子值可以是 1 到 t + 1 之间的整数(包含 1 和 t + 1)。游戏开始时,因子值为 1。销毁 pi (1 ≤ i ≤ t) 个人物后,因子设置为 i + 1,因此认为要销毁的第 (pi + 1) 个人物的因子等于 i + 1。
你的任务是确定 Vasya 摧毁所有人物后可以获得的最大分数。考虑到瓦夏是如此强大,他可以按照他选择的任何顺序摧毁人物。
输入
第一行包含唯一的整数 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 指定器。
输出
打印唯一的数字——Vasya 可以获得的最大分数。
示例
输入 #1
1 5 10 2 3 6
输出 #1
70
输入 #2
2 3 8 5 10 1 20
输出 #2
74
注意
在第一个示例中,Vasya 首先摧毁了三个人物并获得 3·1·10 = 30 分。然后因子将变为等于 2,在摧毁最后两个数字后,瓦夏将获得 2·2·10 = 40 分。结果 Vasya 将得到 70 分。
在第二个示例中,所有 8 个人物将以因子 1 被摧毁,因此 Vasya 将获得 (3·8 + 5·10)·1 = 74 分。