Bajtazar lives in a rented apartment. One of his duties is to record the state of $n$ water meters in the apartment every month. The initial state of the $i$-th meter, as recorded by the landlord, is $s_i$ cubic bajtometers of water. As is well known, not all water is the same, and one cubic bajtometer of water may have a different price depending on the meter. Specifically, one cubic bajtometer of water measured by the $i$-th meter costs $c_i$ bajtalars.

Bajtazar has been living in this apartment for $m$ months. For each month, he has $n$ values recorded that he would like to present to the landlord as the meter readings for that month. First, however, he must organize his notes. For each month, he wants to assign the recorded values to the meters. The order in which the recorded values are assigned to the individual meters does not have to be the same in different months. However, it cannot be the case that the value assigned to the same meter in a given month is smaller than in the previous month (or smaller than the initial state of the meter recorded by the landlord).

The landlord will charge Bajtazar a total fee for the water consumed, calculated based on the values assigned to the meters for the last month. Specifically, the total fee is the sum of the fees for the water measured by the individual meters, and the fee for the water measured by the $i$-th meter is $c_i$ times the difference between the value assigned to the $i$-th meter for the last month and $s_i$.

Determine the minimum total fee for the water consumed that Bajtazar can obtain by assigning the read values to the meters in a way that complies with the above conditions, or detect that such an assignment is not possible.

Input

The first line of the input contains two positive integers $n$ and $m$ ($n \cdot m \le 300\,000$).

The second line contains $n$ integers $c_i$ ($1 \le c_i \le 1\,000\,000$) representing the cost in bajtalars of one cubic bajtometer of water measured by the individual meters.

The third line contains $n$ integers $s_i$ ($0 \le s_i \le 1\,000\,000$) representing the initial states of the individual meters (in cubic bajtometers).

The next $m$ lines contain the readings from consecutive months. The $i$-th of these lines contains $n$ integers $a_{i,j}$ ($0 \le a_{i,j} \le 1\,000\,000$) representing the values recorded by Bajtazar for the $i$-th month.

Output

If it is not possible to assign the read values to the meters in accordance with the conditions of the problem, output the single word NIE.

Otherwise, output a single integer representing the minimum total fee (in bajtalars) that Bajtazar can obtain.

Examples

Input 1

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

Output 1

25

Note 1

The initial states of the meters are: 3, 2, 4, 7. The values read in the first month can be assigned to the individual meters in the following order: 3, 10, 5, 7. Then, the values read in the second month can be assigned to the individual meters in the following order: 4, 10, 6, 9. The total fee is then equal to $3 \cdot (4 - 3) + 1 \cdot (10 - 2) + 4 \cdot (6 - 4) + 3 \cdot (9 - 7) = 25$. It can be verified that it is not possible to obtain a smaller total fee.

Subtasks