Background

Patchouli is a magic user with asthma.

Problem Description

It is well known that different spells require chanting different lengths of incantations $a_i$ but also yield different powers $b_i$. Additionally, casting a spell can affect the power of the next spell cast, denoted as $w_{i,j}$ (i.e., after using the $i$-th spell, the power of the $j$-th spell will become $b_j + w_{i,j}$, affecting only the next spell).
(Of course, some spells might reduce the length of the incantation or have healing effects, and spells cannot be reused.)

Patchouli now knows the impact of each spell on the next one, as well as the length of the incantation and the power generated by each spell. Also, since spells with larger numbers are more advanced than those with smaller numbers, a spell can only be used after spells with numbers not greater than itself to ensure the continuity of the magic. She wants to know the maximum power that can be generated by chanting an incantation of length $m$. (To avoid another defeat due to asthma during a battle.)

(The order of numbers is the same as the given order.)

Input Format

The first line contains two positive integers $n, m$, indicating there are $n$ types of spells and the length of the incantation to be chanted is $m$.

The next $n$ lines: each line contains two positive integers $a_i, b_i$, representing the length of the incantation and the power of the spell.

The following $n$ lines: each line contains $n$ integers, where the $i$-th line and $j$-th column represent the additional value $w_{i,j}$ generated when the $i$-th spell is used after the $j$-th spell.

Output Format

A single integer representing the maximum power that can be generated.
(If it is impossible to form an incantation of length $m$, output -1.)

Sample Input and Output

Sample Input #1

2 5
3 3
2 2
1 2
3 4

Sample Output #1

7

Sample Input #2

2 6
3 3
2 2
1 2
3 4

Sample Output #2

-1

Notes

For 20% of the data, it is guaranteed that $a_i = 1$.

For another 20% of the data, it is guaranteed that all numbers are positive integers.

For 100% of the data, $1 \le n \le 50$, $|a_i|, |b_i|, |w_{i,j}| \le 50$, $|m| \le 2500$, and it is guaranteed that the numbers involved in the calculations are within the int range.

见题面 Input 部分

见题面 Output 部分