结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某工厂的设备科收到 $B$ 批检修工单，批次编号为 $1 \sim B$。批 $b$ 包含 $k_b$ 台设备，其中第 $j$ 台设备的检修耗时为 $t_{b,j}$，重要度为 $w_{b,j}$。全部设备由同一组检修工从时刻 $0$ 起串行检修，同一时刻只能检修一台设备。

检修规程对执行顺序有如下要求：同一批内的设备必须按工单给定的顺序依次检修；一批一旦开始检修，就必须连续做完该批的全部设备，中途不得插入其他批次的设备；而批与批之间的先后次序可以自由安排。

设设备 $i$ 的完工时刻为 $C_i$（即该设备检修完成的时刻），检修科为这批工单核算的总代价为所有设备的 $w_i \cdot C_i$ 之和，即 $\sum_i w_i \cdot C_i$。

请核算：如何安排批次的执行顺序，才能使总代价最小。输出最小总代价，以及达到该最小代价的批次执行顺序（一个批号序列）。

输入格式

从文件 batch.in 中读入数据。

• 第一行一个整数 $B$，表示批次的数量；
• 接下来依次给出 $B$ 个批次的工单。批 $b$ 的工单格式为：第一行一个整数 $k_b$，表示该批的设备数量；随后 $k_b$ 行，每行两个整数 $t_{b,j}, w_{b,j}$，依次表示该批第 $j$ 台设备的检修耗时与重要度。

输出格式

输出到文件 batch.out 中。

• 第一行一个整数，表示最小总代价；
• 第二行 $B$ 个整数，用一个空格隔开，表示达到最小总代价的批次执行顺序（按执行先后给出的批号序列）。

样例

3
2
5 1
1 3
1
4 4
2
2 2
3 1

94
2 1 3

样例 1 解释

按 $2, 1, 3$ 的顺序执行：先做批 $2$，唯一一台设备在时刻 $4$ 完工，代价 $4 \times 4 = 16$；再做批 $1$，两台设备分别在时刻 $9$、$10$ 完工，代价 $1 \times 9 + 3 \times 10 = 39$；最后做批 $3$，两台设备分别在时刻 $12$、$15$ 完工，代价 $2 \times 12 + 1 \times 15 = 39$。总代价 $16 + 39 + 39 = 94$。

4
1
1 1
1
3 6
2
2 5
1 4
1
2 5

104
3 4 2 1

样例 2 解释

按 $3, 4, 2, 1$ 的顺序执行：批 $3$ 的两台设备在时刻 $2$、$3$ 完工，代价 $5 \times 2 + 4 \times 3 = 22$；批 $4$ 的设备在时刻 $5$ 完工，代价 $5 \times 5 = 25$；批 $2$ 的设备在时刻 $8$ 完工，代价 $6 \times 8 = 48$；批 $1$ 的设备在时刻 $9$ 完工，代价 $1 \times 9 = 9$。总代价 $22 + 25 + 48 + 9 = 104$。

2
3
4 2
1 1
2 3
2
3 2
2 1

66
1 2

样例 3 解释

按 $1, 2$ 的顺序执行：批 $1$ 的三台设备分别在时刻 $4$、$5$、$7$ 完工，代价 $2 \times 4 + 1 \times 5 + 3 \times 7 = 34$；批 $2$ 的两台设备分别在时刻 $10$、$12$ 完工，代价 $2 \times 10 + 1 \times 12 = 32$。总代价 $34 + 32 = 66$。若按 $2, 1$ 的顺序执行，批 $2$ 的代价为 $2 \times 3 + 1 \times 5 = 11$，批 $1$ 的三台设备完工时刻变为 $9$、$10$、$12$，代价为 $2 \times 9 + 1 \times 10 + 3 \times 12 = 64$，总代价 $75$。

数据范围

对于所有测试数据，保证：

• $1 \le B \le 10^5$；
• $1 \le k_b$，且 $\sum_{b=1}^{B} k_b \le 2 \times 10^5$；
• $1 \le t_{b,j}, w_{b,j} \le 10^4$；
• 各批次的 $\sum_j t_{b,j}$ 与 $\sum_j w_{b,j}$ 之比两两不同。

各测试点的约束如下：

• 特殊性质 A：每批只有一台设备，即 $k_b = 1$。