题目背景

帕秋莉是一个有哮喘病的魔法使。

题目描述

众所周知，不同的魔法会需要念不同长度咒语$a_i$但也会产生不同的威力$b_i$。同时，在发动过一个魔法后也会对接下来发动的一个魔法产生影响$w_{i,j}$（即在用完第$i$种魔法后第$j$种魔法的威力会变为$b_j + w_{i.j}$，而且只会影响到下一个魔法）。 （当然也可能有魔法会减少咒语长度或者产生治愈的效果的魔法，魔法不可重复使用）

帕秋莉现在知道使用每种魔法后对接下来一种魔法的影响，以及每种魔法需要念的咒语长度和产生的威力，同时，由于编号大的魔法比编号小的魔法高级，所以一个魔法只有在编号不大于自己的魔法后使用才能保证魔法的连续性），现在她想知道念出长度为$m$的咒语最大能产生多少威力。(以免下次在战斗中又因为哮喘病发作而惨败)

(编号顺序即给出的顺序)

输入格式

第一行：两个正整数$n,m$，表示一共有$n$种魔法，念出长度为$m$咒语。

接下来的$n$行：每行两个正整数$a_i,b_i$，表示咒语的长度以及魔法的威力。

接下来的$n$行 ： 每行$n$个整数，第$i$行，第$j$列，代表第$i$种魔法在第$j$种魔法后使用产生的附加值$w_{i,j}$。

输出格式

一个整数，表示最大能产生的威力。 （如果无论如何都无法组成长度为$m$的咒语，则输出-1）

2 5
3 3
2 2
1 2
3 4

7

2 6
3 3
2 2
1 2
3 4

-1

提示

对于20%的数据，保证$a_i$ = 1

对于另外20%的数据，保证所有数字均为正整数。

对于100%的数据，$1 \le n \le 50, |a_i|,|b_i|, |w_{i,j}|\le 50, |m| \le 2500$，保证运算过程中的数字大小均在int范围内(废话...)。