在我七岁生日那天,我父亲告诉我我是谁。
``现在你七岁了,我已经退休了。从今天起,你就是七年教会的领袖了。
根据七岁教会的戒律,七岁教会的领袖只有在七岁期间才可以进行传教活动。
用这艘宇宙飞船将七年教堂的奇迹传播给更多的人。 ”
为了将7年的宗教传播给更多的人,“他”收集了身边星星的信息。
围绕“他的”星星,
有n 个行星,并且该行星是
我发现它们的编号为 1, ... , n 。
惑星i 来自行星
要在j之间移动,
还发现需要w_i_j (年)。
而且事实证明,他在每个星球上能停留七岁的时间,也就是他能做传教工作的时间,是不同的。
在每个星球上,宇宙日历l_i年1月1日00:00:00以降r_i只要在 2019 年 1 月 1 日 00:00:00 之前,您就可以年满 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