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$