Background

Patchouli is a magician who has asthma.

Problem Description

As everyone knows, different kinds of magic require chanting spells of different lengths $a_i$, and they also produce different power $b_i$. At the same time, after casting one magic spell, it will affect the next spell cast: $w_{i,j}$. That is, after using the $i$-th kind of magic, the power of the $j$-th kind of magic becomes $b_j + w_{i,j}$, and it only affects the very next spell. (Of course, some magic may reduce the spell length, or have healing effects. Magic cannot be used repeatedly.)

Patchouli now knows the effect of each magic on the next one, as well as the spell length and base power of each magic. Also, since magic with a larger index is more advanced than magic with a smaller index (the index order is the given order), a magic spell can only be used after a magic whose index is not greater than its own, in order to keep the casting sequence continuous. Now she wants to know: with a total spell length of $m$, what is the maximum power that can be produced? (So that she will not suffer a terrible defeat again in battle due to an asthma attack.)

Input Format

The first line contains two positive integers $n, m$, meaning there are $n$ kinds of magic in total, and the total spell length is $m$.

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

The next $n$ lines: each line contains $n$ integers. The number in row $i$, column $j$ denotes the additional value $w_{i,j}$ produced when using the $j$-th kind of magic after the $i$-th kind of magic.

Output Format

Output one integer, the maximum power that can be produced. If it is impossible to form a total spell length of $m$ no matter what, output -1.

2 5
3 3
2 2
1 2
3 4

7

2 6
3 3
2 2
1 2
3 4

-1

Hint

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

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

For $100\%$ of the testdata, $1 \le n \le 50$, $|a_i|, |b_i|, |w_{i,j}| \le 50$, $|m| \le 2500$. It is guaranteed that all numbers during computation fit within the range of int.

Translated by ChatGPT 5