2024 软件学院 ACM 集训队筛选赛
Problem G. 1+2=无困
十座炮塔共计开六炮，最后一炮打在天上，炸出一道裂缝。硕大一个鼠标箭头从中钻出，往甲板移动。
小熊和 a7 骑在那个箭头上跟着下来。一人带着 ho 佬的草稿本；一人拿着一台笔记本，打开的是 Haru 的博客。小熊把草稿本盖在笔记本的键盘上，然后笔记本上的网页开始自己动了起来。过会，草稿本和笔记本屏幕映着相同的题面。
面对这么混乱、奇诡的一切，pwp 只能相信自己是在做梦。
而草稿本和笔记本映出的题面是……
有一张有 n 个节点的有向图，初始时没有任何边。每个节点均拥有一个长度为 l 的权值序列，第 i 个点的权值序列中第 j 个权值为 a_{i, j}。每个节点还各有一个费用 c_i。
你有两种操作可以执行，次数不限（可以为 0 次）：
- 选择一个节点 u 的权值序列中某个权值 a_{u, i} 并选择一个数值 j，花费 j 来将该权值增加 j。
- 选择一个节点 u 的权值序列中某个权值 a_{u, i}，同时选择另一个节点 v，如果 a_{u, i} \ge a_{v, i}，则花费 c_u 连一条从 u 到 v 的有向边。
求出让节点 n 可达节点 1 的最小费用。
输入
第一行输入两个整数 n 和 l。（2 \le n \le 2 \times 10^5, 1 \le l \le 10^5, n \cdot l \le 2 \times 10^5）
第二行输入 n 个整数 c_i。（1 \le c_i \le 10^9）
接下来 n 行每行输入 l 个整数，第 i 行输入 a_{i, 1}, a_{i, 2}, \dots, a_{i, l}。（1 \le a_{i, j} \le 10^9）
输出
输出一行一个整数表示答案。
样例
| 标准输入 复制文本 |
3 3 2 3 1 2 9 9 6 1 7 1 2 1 |
| 标准输出 复制文本 |
2 |
| 标准输入 复制文本 |
4 2 2 8 3 5 18 24 17 10 1 10 1 1 |
| 标准输出 复制文本 |
17 |
| 标准输入 复制文本 |
6 3 21412674 3212925 172015806 250849370 306960171 333018900 950000001 950000001 950000001 821757276 783362401 760000001 570000001 700246226 600757652 380000001 423513575 474035234 315201473 300580025 287023445 1 1 1 |
| 标准输出 复制文本 |
1224474550 |
登录以提交代码。