MapleStory

Sangwon will play MapleStory during winter break. Since he will be busy once the semester starts, he wants to gain as many levels as possible during the break.

MapleStory has many hunting grounds. Each hunting ground has various characteristics such as the minimum level required to enter, the terrain, the monster level, the number of monsters, and burning. Since experience is what matters most to Sangwon, he simplified each hunting ground to its minimum experience required to enter and the experience gained per $1$ minute. After he starts hunting, every minute he decides whether to keep hunting at his current ground or move to another ground. Sangwon spent all his money on cosmetic items and cannot teleport, so he walks between hunting grounds. He cannot hunt while moving between grounds, so he gains no experience then.

Since his character starts with $0$ experience, he chooses one of the hunting grounds whose minimum experience required to enter is $0$ and starts hunting there. Report the maximum experience Sangwon can gain during the break.

The first line gives the number of hunting grounds $N$ ($1 \le N \le 200$) and the length of the break in minutes $T$ ($1 \le T \le 1\,000$).

The next $N$ lines give the characteristics of the $i$-th hunting ground: the minimum experience required to enter $c_i$ and the experience gained per $1$ minute $e_i$. ($0 \le c_i, e_i \le 1\,000\,000$)

The next $N$ lines give the time required to move between hunting grounds. The $j$-th number in the $i$-th line is $t_{i,j}$, the time in minutes required to move from hunting ground $i$ to hunting ground $j$ and enter it. ($1 \le t_{i,j} \le 1\,000$, $t_{i,j}=t_{j,i}$, $t_{i,i}=0$)

There is always at least one hunting ground whose minimum experience required to enter $c_i$ is $0$.

Print the maximum experience Sangwon can gain during the break.