AT_arc056_d [ARC056D] サケノミ

你来到了一个与众不同的酒吧。在这个酒吧里，有 $N$ 种饮品，你一开始会得到 $N$ 个玻璃杯。第 $i$ 个玻璃杯对应第 $i$ 种饮品，只能倒入第 $i$ 种饮品。每种饮品都有一个确定的美味度 $w_i$。一开始，所有玻璃杯都是空的。 每种饮品会在若干个特定时刻被补充。也就是说，在时间 $t_{i,j}\ (1 \leq j \leq M_i)$ 时，如果第 $i$ 个玻璃杯是空的，就会倒入第 $i$ 种饮品。 你可以在任意奇数时刻，将所有玻璃杯中的饮品全部喝光。禁止只喝部分饮品。每次喝下的饮品的美味度会累加到总和中。需要注意的是，即使多次喝到同一种饮品，其美味度也会重复计算。 请编写程序，求出可以获得的美味度总和的最大值。

输入通过标准输入给出，格式如下： > $N$ $w_1$ ... $w_N$ $M_1$ $t_{1,1}$ ... $t_{1,M_1}$ : $M_N$ $t_{N,1}$ ... $t_{N,M_N}$

输出一行，表示美味度总和的最大值。

## 限制条件 - $1 \leq N \leq 5 \times 10^5$ - $2 \leq t_{i,j} \leq 10^6$ - $t_{i,j} < t_{i,j+1}$ - $t_{i,j}$ 是偶数 - $\sum M_i \leq 5 \times 10^5$ - $1 \leq M_i$ - $-10^9 \leq w_i \leq 10^9$ ## 部分得分 - 若所有测试用例满足 $t_{i,j} \leq 1,000$ 且 $N \leq 1,000$，则可获得部分分 $30$ 分。 ## 样例说明 1 在时刻 $9$ 和 $11$ 将所有玻璃杯中的饮品喝光。时刻 $9$ 时，3 种饮品都已倒入，因此获得美味度 $2+5-6=1$。时刻 $11$ 时，只有第 2 种饮品被倒入，因此获得美味度 $5$。总共获得 $6$。 由 ChatGPT 4.1 翻译