【题目描述】

有一个 $n \times m$ 的网格图，从上到下第 $i$ 行从左到右第 $j$ 列的格子为 $(i, j)$。

第 $i$ 行前 $a_i$ 个格子为黑色，即 $(i, 1), (i, 2), \ldots, (i, a_i)$，其余为白色。第 $i$ 行相邻两列黑色格子之间有一条边权为 $v_i$ 的无向边。

你需要进行 $n - 1$ 次操作，使任意两个黑色格子互相可达，操作为选择三个整数 $x, y, z$，在 $(x, z)$ 和 $(y, z)$ 间添加一条边权为 $w$ 的边（$w$ 为常数），存在如下限制：

• $1 \leq x < y \leq n, 1 \leq z \leq m;$
• $(x, z)$ 和 $(y, z)$ 均为黑色格子；
• 对于 $x < i < y, (i, z)$ 为白色格子。

你需要最小化共 $S = \sum a_i$ 个黑色格子之间的两两距离之和。

【输入格式】

输入的第一行包含一个非负整数 $c$，表示测试点编号。$c = 0$ 表示该测试点为样例。

第二行包含三个正整数 $n, m, w$，表示网格大小和常数 $w$。

接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i, v_i$，分别表示第 $i$ 行黑色格子数量和内部边权。

【输出格式】

输出仅一行一个正整数，表示最小距离和。

0
1 5 1
5 1

20

【数据规模与约定】

对于所有测试数据，保证：$1 \leq n \leq 60$，$1 \leq v_i, w \leq 10^6$，$1 \leq a_i \leq m \leq 3000$，$1 \leq S \leq 3000$。

特殊性质 A：对于 $1 \leq i < n$，保证 $a_i \leq a_{i+1}$。