Spellcasting Optimization

You are given n spells. Each spell i requires reciting a spell incantation of length \(a_i\) and produces a base power of \(b_i\). Moreover, when a spell \(i\) is cast immediately before a spell \(j\), the power of spell \(j\) is modified by an additive term \(w_{i,j}\); that is, if spell \(j\) is cast immediately after spell \(i\), its effective power becomes \(b_j + w_{i,j}\). Note that the effect \(w_{i,j}\) influences only the very next spell.

In addition, due to the hierarchy of spells (a spell with a higher index is more advanced than one with a lower index), you are allowed to cast spells only in an increasing order of their indices. (In other words, if spell \(j\) appears after spell \(i\) in your sequence then \(i \lt j\).) Each spell can be used at most once.

Your task is to select a sequence of spells (possibly of length 1) so that the total incantation length is exactly \(m\) (i.e. \(\sum a_i = m\)). The total power gained is defined as the sum of powers of all spells in the sequence, where for every spell (except the first) the power is \(b_j + w_{i,j}\) if it immediately follows spell \(i\). That is, if the chosen sequence is \(s_1, s_2, \dots, s_k\) then the total power is:

[ \text{Total Power} = b_{s_1} + \sum_{t=2}^{k} \Big( b_{s_t} + w_{s_{t-1}, s_t} \Big). ]

Compute the maximum total power you can obtain by reciting spells with exactly total incantation length \(m\>.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n \leq N_{max}) \) representing the number of spells and the required total incantation length, respectively.

The next \(n\) lines each contain two integers \(a_i\) and \(b_i\), where \(a_i\) is the incantation length required by the \(i\)-th spell and \(b_i\) is its base power. Note that \(a_i\) or \(b_i\) can be negative.

The following \(n\) lines each contain \(n\) integers. The \(i\)-th of these lines contains \(w_{i,1}, w_{i,2}, \dots, w_{i,n}\), where \(w_{i,j}\) is the additional power effect on spell \(j\) when it immediately follows spell \(i\). You may assume that the effect is only applied when spell \(j\) is cast right after spell \(i\>.

outputFormat

Output a single integer, the maximum total power that can be obtained under the given conditions. It is guaranteed that at least one sequence of spells can yield a total incantation length exactly equal to \(m\).

sample

3 10
3 5
4 6
3 5
0 1 -1
2 0 3
1 4 0

20