Time Limit: 3 sec / Memory Limit: 128 MB
7歳の誕生日に"彼"は父から告げられた.
「お前が7歳になったということは,私はもう引退だ.今日からお前が7歳教の長だ.
7歳教の戒律により,7歳教の長が7歳の間だけ布教活動を行うことが認められている.
この宇宙船を使って,よりたくさんの人々に7歳教の素晴らしさを広めてきなさい.」
7歳教をよりたくさんの人に広めるために"彼"は,自分の周りの星についての情報を集めた.
"彼"の星の周りには,n 個の惑星があり,惑星は 1, ... , n で番号付けされていることがわかった.
惑星i から 惑星jの間を移動するには,w_i_j (年)の時間がかかることもわかった.
そして,それぞれの星で彼が7歳でいられる時間,つまり布教活動できる時間が異なることがわかった.
それぞれの惑星上では,宇宙暦l_i年1月1日00:00:00以降r_i年1月1日00:00:00より前までの時間帯であれば7歳でいられる.
たとえ一度ある星で7歳以外の年齢になっても,その星で後から7歳になった場合や,別の星で7歳になれば布教活動を再開することができる.
しかしどの星でどれくらい,そしてどの順序で布教活動を行えばより多くの人に7歳教を伝えることができるのか,
"彼"にはわからなかった.そこで"彼"はプログラミングが得意なあなたに助けを求めることにした.
現在は宇宙暦0年1月1日00:00:00であり,"彼"は惑星 s にいる.
惑星間を最適に移動・滞在した場合に布教活動が行える最長の年数,
つまり"彼"が7歳でかつ惑星で過ごす最長の年数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)
この問題の判定には,50 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.
- すべての i, j に対して w_{ij} = 0
入出力例
入力例 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