Bajtazar 住在租来的公寓里。他的职责之一是每月记录公寓中 $n$ 个水表的读数。房东记录的第 $i$ 个水表的初始状态为 $s_i$ 立方米。众所周知，水与水不同，每立方米水根据水表的不同可能有不同的价格。更准确地说，第 $i$ 个水表计量的每立方米水价格为 $c_i$ 巴伊塔拉（bajtalar）。

Bajtazar 在这间公寓已经住了 $m$ 个月。对于每个月，他都有 $n$ 个记录值，他想把这些值作为该月读取的水表读数提交给房东。但他首先必须整理他的记录。对于每个月，他需要将记录的值分配给各个水表。记录值分配给各个水表的顺序在不同月份不必相同。然而，分配给同一个水表的某个月的值不能小于前一个月的值（也不能小于房东记录的水表初始状态）。

房东将根据最后一个月分配给水表的值，向 Bajtazar 收取总水费。更准确地说，总费用是各水表计量的水费之和，而第 $i$ 个水表计量的水费为 $c_i$ 乘以（最后一个月分配给第 $i$ 个水表的值与 $s_i$ 之间的差值）。

请计算 Bajtazar 在符合上述条件的情况下，分配读数所能获得的最小总费用，或者判断这种分配是不可能的。

输入格式

第一行包含两个正整数 $n$ 和 $m$ ($n \cdot m \le 300\,000$)。

第二行包含 $n$ 个整数 $c_i$ ($1 \le c_i \le 1\,000\,000$)，表示第 $i$ 个水表计量的每立方米水的价格。

第三行包含 $n$ 个整数 $s_i$ ($0 \le s_i \le 1\,000\,000$)，表示各水表的初始状态（单位为立方米）。

接下来的 $m$ 行包含后续各个月的读数。第 $i$ 行包含 $n$ 个整数 $a_{i,j}$ ($0 \le a_{i,j} \le 1\,000\,000$)，表示 Bajtazar 为第 $i$ 个月记录的值。

输出格式

如果无法按照题目要求将读数分配给水表，请输出一行 NIE。

否则，请输出一个整数，表示 Bajtazar 可以获得的最小总费用（单位为巴伊塔拉）。

样例

样例输入 1

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

输出格式 1

25

说明 1

水表的初始状态为：3, 2, 4, 7。第一个月的读数可以按以下顺序分配给各水表：3, 10, 5, 7。随后，第二个月的读数可以按以下顺序分配给各水表：4, 10, 6, 9。此时总费用等于 $3 \cdot (4 - 3) + 1 \cdot (10 - 2) + 4 \cdot (6 - 4) + 3 \cdot (9 - 7) = 25$。可以验证，无法获得更小的总费用。

样例测试

测试 0 即为上述样例。此外：

1. $n = m = 1, c_i = 1\,000\,000, s_i = 0$ ($1 \le i \le n$), $a_{1,1} = 1\,000\,000$；输出：$1\,000\,000\,000\,000$
2. $n = 6, m = 10, c_i = i + 1, s_i = 0$ ($1 \le i \le n$), $a_{i,j} = j$ ($1 \le i \le m, 1 \le j \le n$)；输出：$77$
3. $n = 150\,000, m = 2, c_i = 1, s_i = 2 \cdot i$ ($1 \le i \le n$), $a_{i,j} = i \cdot j$ ($1 \le i \le m, 1 \le j \le n$)；输出：NIE
4. $n = 150\,000, m = 2, c_i = i, s_i = 0, a_{i,j} = 30 \cdot i + (j \pmod{17}) + 1$ ($1 \le i \le m, 1 \le j \le n$)；输出：$744\,488\,775\,021$

评分

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。