← 返回题目列表

AtCoder · kupc2013_f

F. 7岁教学

中文机器翻译题面 查看原题

在我七岁生日那天,我父亲告诉我我是谁。

``现在你七岁了,我已经退休了。从今天起,你就是七年教会的领袖了。
根据七岁教会的戒律,七岁教会的领袖只有在七岁期间才可以进行传教活动。
用这艘宇宙飞船将七年教堂的奇迹传播给更多的人。 ”

为了将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