F - ７歳教

７歳の誕生日に"彼"は父から告げられた．

「お前が７歳になったということは，私はもう引退だ．今日からお前が７歳教の長だ．
７歳教の戒律により，７歳教の長が７歳の間だけ布教活動を行うことが認められている．
この宇宙船を使って，よりたくさんの人々に７歳教の素晴らしさを広めてきなさい．」

７歳教をよりたくさんの人に広めるために"彼"は，自分の周りの星についての情報を集めた．
"彼"の星の周りには，n 個の惑星があり，惑星は 1, ... , n で番号付けされていることがわかった．
惑星i から 惑星jの間を移動するには，w_i_j (年)の時間がかかることもわかった．

そして，それぞれの星で彼が７歳でいられる時間，つまり布教活動できる時間が異なることがわかった．
それぞれの惑星上では，宇宙暦l_i年1月1日00:00:00以降r_i年1月1日00:00:00より前までの時間帯であれば7歳でいられる．
たとえ一度ある星で７歳以外の年齢になっても，その星で後から７歳になった場合や，別の星で７歳になれば布教活動を再開することができる．

しかしどの星でどれくらい，そしてどの順序で布教活動を行えばより多くの人に７歳教を伝えることができるのか，
"彼"にはわからなかった．そこで"彼"はプログラミングが得意なあなたに助けを求めることにした．

現在は宇宙暦0年1月1日00:00:00であり，"彼"は惑星 s にいる． 惑星間を最適に移動・滞在した場合に布教活動が行える最長の年数，
つまり"彼"が７歳でかつ惑星で過ごす最長の年数Tを求めてあげよう． ただし，年数Tには移動時間は含まれない．

入力形式

入力は以下の形式で与えられる．

n s
l_1 r_1
     ...     
l_{n} r_{n}
w_{1,1}  w_{1,2} ... w_{1,n}
     ...     
w_{n,1} w_{n,2} ... w_{n,n}

n は惑星の個数である．s は主人公が最初にいる惑星をあらわす．
l_i と r_i はそれぞれ，惑星i での7歳でいられる時間帯の下限と上限をあらわす．
w_i_j は，惑星iから惑星jを移動するのにかかる時間をあらわす．
入力はすべて整数である．

出力形式

答えTを出力せよ．

制約

• 1 ≤ n ≤ 500
• 1 ≤ s ≤ n
• 0 ≤ l_i < r_i ≤ 10^8
• 0 ≤ w_{ij} ≤ 10^8 (i ≠j)
• w_{ij} = 0 (i = j)

入出力例

入力例 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