AT_kupc2013_f.７歳教

有 $n$ 个城市，从第 $i$ 个城市到第 $j$ 个城市需要花费 $w_{i,j}$ 天的时间。每个城市都有两个参数 $l_i$ 和 $r_i$。如果你在这个城市待的时间与 $[l_i,r_i-1]$ 这段时间有交集，则交集部分的天数会被加到你的积分中。你现在在第 $s$ 个城市。请求出你可以获得的积分的最大值。（今天是第 $0$ 天，目前积分为 $0$）

第一行：$n,s$

接下来 $n$ 行：第 $i$ 行为 $l_i,r_i$

接下来 $n$ 行：第 $i$ 行为 $w_{i,1},w_{i,2},...,w_{i,n}$

（输入均为整数）

输出答案。

输入输出样例

输入 #1

2 1
0 100
150 250
0 100
100 0

输出 #1

150

输入 #2

5 1
7 44
10 49
38 48
11 23
11 30
0 1 7 2 7
10 0 3 8 10
4 8 0 2 5
3 2 1 0 4
8 4 3 3 0

输出 #2

41

数据规模与约定

$1 \le n \le 500$

$1 \le s \le n$

$0 \le l_i \lt r_i \le 10^8$

$0 \le w_{i,j} \le 10^8(i \neq j)$

$w_{i,i} = 0$