题目描述

题目译自XXII Olimpiada Informatyczna — II etap Trzy Wieże

Bajtazar 租住在一套公寓里，每月需记录公寓内 $n$ 个水表的读数。房东记录的第 $i$ 个水表初始读数为 $s_i$ 拜托立方米。不同水表的水价各异，第 $i$ 个水表计量的每拜托立方米水费用为 $c_i$ 拜托拉。

Bajtazar 已在此居住 $m$ 个月，每月记录了 $n$ 个读数，希望提交给房东作为当月水表数据。但他需先整理记录：每月将 $n$ 个读数分配到水表，分配顺序在不同月份可不同，但同一水表在后一月份的读数不得小于前一月份或初始读数。

房东将根据最后月份的分配读数计算 Bajtazar 的总水费，即各水表费用之和，其中第 $i$ 个水表费用为 $c_i$ 乘以最后月份读数与 $s_i$ 的差值。你的任务是计算 Bajtazar 能获得的最小总水费，或判断是否无法按上述条件分配读数。

输入格式

第一行包含两个正整数 $n$, $m$ $(n \cdot m \leq 300000)$，分别表示水表数量和月份数。

第二行包含 $n$ 个整数 $c_i$ $(1 \leq c_i \leq 1000000)$，表示第 $i$ 个水表每拜托立方米的费用（单位：拜托拉）。

第三行包含 $n$ 个整数 $s_i$ $(0 \leq s_i \leq 1000000)$，表示第 $i$ 个水表的初始读数（单位：拜托立方米）。

接下来的 $m$ 行，每行包含 $n$ 个整数 $a_{i,j}$ $(0 \leq a_{i,j} \leq 1000000)$，表示第 $i$ 个月的第 $j$ 个记录值。

输出格式

若无法按条件分配读数，输出 NIE。

否则，输出一个整数，表示 Bajtazar 能获得的最小总水费（单位：拜托拉）。

样例

输入：

4 2
3 1 4 3
3 2 4 7
5 10 3 7
4 6 10 9

输出：

25

初始水表读数为 $3$, $2$, $4$, $7$。

第一个月读数 $[5, 10, 3, 7]$ 可分配为水表顺序 $3$, $10$, $5$, $7$。 第二个月读数 $[4, 6, 10, 9]$ 可分配为水表顺序 $4$, $10$, $6$, $9$。 总水费为 $3 \cdot (4-3) + 1 \cdot (10-2) + 4 \cdot (6-4) + 3 \cdot (9-7) = 25$。

可验证这是最小水费。

附加样例

• $n=m=1$，$c_i = 1000000$, $s_i = 0$ 对于 $1 \leq i \leq n$，$a_{1,1} = 1000000$，答案为 $1000000000000$。
• $n=6$, $m=10$，$c_i = i+1$, $s_i = 0$ 对于 $1 \leq i \leq n$，$a_{i,j} = j$ 对于 $1 \leq i \leq m$, $1 \leq j \leq n$，答案为 $77$。
• $n=150000$, $m=2$，$c_i = 1$, $s_i = 2 \cdot i$ 对于 $1 \leq i \leq n$，$a_{i,j} = i \cdot j$ 对于 $1 \leq i \leq m$, $1 \leq j \leq n$，答案为 NIE。
• $n=150000$, $m=2$，$c_i = i$, $s_i = 0$，$a_{i,j} = 30 \cdot i + (j \bmod 17) + 1$ 对于 $1 \leq i \leq m$, $1 \leq j \leq n$，答案为 $744488775021$。

数据范围与提示

详细子任务附加限制及分值如下表所示。