Geometry Horse

题目描述

瓦夏在玩“几何小马”游戏。

游戏的目标是摧毁游戏世界里的几何图形。破坏每个图形会根据图形类型和当前因子值获得一定的分数。

游戏中共有 $n$ 种类型的几何图形。对于每种类型的图形，已知该类型的图形数量 $k_{i}$，以及单个图形的分值 $c_{i}$。玩家每摧毁一个 $i$ 类型的图形，将获得 $c_{i}·f$ 分，其中 $f$ 是当前的因子值。因子值可以为 $1$ 到 $t+1$ 之间的整数（含 $1$ 和 $t+1$）。游戏开始时，因子值为 $1$。当摧毁了 $p_{i}$ $(1 \leq i \leq t)$ 个图形后，因子值被设置为 $i+1$，也就是说，第 $p_{i}+1$ 个被摧毁的图形将以因子 $i+1$ 计分。

你的任务是求出瓦夏能获得的最大分数，假设他可以任意选择摧毁图形的顺序。

输入格式

第一行包含一个整数 $n$ $(1\leq n\leq 100)$，表示图形类型的数量。

接下来的 $n$ 行，每行包含两个用空格分隔的整数 $k_{i}$ 和 $c_{i}$ $(1\leq k_{i}\leq 10^{9}, 0\leq c_{i}\leq 1000)$，表示第 $i$ 类型图形的数量和单个该类型图形的分值。

下一行包含一个整数 $t$ $(1\leq t \leq 100)$，表示因子变化的次数。

最后一行包含 $t$ 个按升序排列的整数 $p_{i}$ $(1\leq p_{1} < p_{2} < ... < p_{t} \leq 10^{12})$，用空格分隔。

请勿在 C++ 中使用 %lld 读写 64 位整数。建议使用 cin、cout 或 %I64d。

输出格式

输出一个整数，表示瓦夏能获得的最大分数。

输入输出样例 #1

输入 #1

1
5 10
2
3 6

输出 #1

70

输入输出样例 #2

输入 #2

2
3 8
5 10
1
20

输出 #2

74

说明/提示

在第一个示例中，瓦夏先摧毁三个图形，每次得 $3·1·10=30$ 分。之后因子变为 $2$，摧毁剩下的两个图形，每次得 $2·2·10=40$ 分。最终瓦夏得到 $70$ 分。

在第二个示例中，所有 $8$ 个图形都以因子 $1$ 被摧毁，总共得分 $(3·8+5·10)·1=74$ 分。

由 ChatGPT 5 翻译