Your company has received a batch of orders. The orders require your company to provide $n$ types of products, numbered $1 \sim n$, where the $i$-th type of product requires $C_i$ units. The company has $m$ employees, numbered $1 \sim m$. Different employees have different capabilities in manufacturing products. A single product must be manufactured entirely by one employee; it cannot be partially manufactured by one employee and then passed on to another.

We use an $m \times n$ matrix $A$ consisting of $0$s and $1$s to describe which products each employee can manufacture. The rows and columns of the matrix are numbered $1 \sim m$ and $1 \sim n$ respectively. $A_{i,j} = 1$ indicates that employee $i$ can manufacture product $j$, and $A_{i,j} = 0$ indicates that employee $i$ cannot manufacture product $j$.

If the company assigns too much work to an employee, that employee becomes unhappy. We use an "anger value" to describe an employee's mood. A higher anger value indicates that the employee is more unhappy, while a lower anger value indicates that the employee is more content. There is a functional relationship between an employee's anger value and the number of products they are assigned to manufacture. Given the different endurance levels of employees, this functional relationship varies from person to person.

For employee $i$, the function relating their anger value to the number of products is a piecewise function with $S_i + 1$ segments. When they manufacture the $1 \sim T_{i,1}$-th product, each product increases their anger value by $W_{i,1}$. When they manufacture the $T_{i,1} + 1 \sim T_{i,2}$-th product, each product increases their anger value by $W_{i,2}$. For convenience, let $T_{i,0} = 0$ and $T_{i, S_i+1} = +\infty$. Then, when they manufacture the $T_{i,j-1} + 1 \sim T_{i,j}$-th product, each product increases their anger value by $W_{i,j}$, where $1 \le j \le S_i + 1$.

Your task is to develop a product allocation plan that satisfies the order requirements while minimizing the sum of all employees' anger values. You only need to output the minimum total anger value.

Input

The first line contains two positive integers $m$ and $n$, representing the number of employees and the number of product types, respectively. The second line contains $n$ positive integers, where the $i$-th integer is $C_i$. The following $m$ lines each contain $n$ integers describing the matrix $A$. The next $m$ parts describe the functional relationship between employee $i$'s anger value and the number of products. Each part consists of three lines: the first line is a non-negative integer $S_i$; the second line contains $S_i$ positive integers, where the $j$-th integer is $T_{i,j}$ (if $S_i = 0$, the input will not contain an empty line, meaning this part consists of only two lines); the third line contains $S_i + 1$ positive integers, where the $j$-th integer is $W_{i,j}$.

Output

Output a single integer representing the minimum total anger value.

Examples

Input 1

2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6

Output 1

24

Constraints

• $30\%$ of the data satisfies $m, n \le 30$.
• Approximately $30\%$ of the data satisfies $S_i = 0$.
• Approximately $30\%$ of the data satisfies $S_i \le 1$ (excluding the $S_i = 0$ cases).
• For $100\%$ of the data, $1 \le m, n \le 250$, $0 \le S_i \le 5$, $0 \le A_{i,j} \le 1$, $0 < T_{i,j} < T_{i,j+1}$, $0 < W_{i,j} < W_{i,j+1}$, and all input values are no greater than $10^5$.