你正处于一条向右无限延伸的走廊中,分为方形房间。您从 $$$1$$$ 房间开始,前往 $$$k$$$ 房间,然后返回 $$$1$$$ 房间。您可以选择 $$$k$$$ 的值。搬到相邻的房间需要花费 $$$1$$$ 秒。
此外,走廊里还有$$$n$$$个陷阱:第$$$i$$$个陷阱位于$$$d_i$$$房间,并且会在你进入$$$房间$$$\boldsymbol{d_i}$$$后$$$s_i$$$秒被激活。一旦陷阱被激活,你就无法进入或离开有该陷阱的房间。
可能的走廊以及您通往 $$$k$$$ 房间并返回的路径的示意图。
确定 $$$k$$$ 的最大值,允许您从 $$$1$$$ 房间前往 $$$k$$$ 房间,然后安全返回 $$$1$$$ 房间。
例如,如果$$$n=1$$$且$$$d_1=2,s_1=2$$$,你可以前往$$$k=2$$$房间并安全返回(此时陷阱将激活$$$1+s_1=1+2=3$$$,它不能阻止你返回)。但如果你试图到达$$$k=3$$$房间,陷阱将在$$$1+s_1=1+2=3$$$时刻激活,阻止你返回(你会在第二个$$$3$$$返回时尝试进入房间$$$2$$$,但激活的陷阱会阻止你)。 $$$k$$$ 任何更大的值也是不可行的。因此,答案是$$$k=2$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 陷阱数量。
每个测试用例描述的以下 $$$n$$$ 行显示两个整数 $$$d_i$$$ 和 $$$s_i$$$ ($$$1 \le d_i, s_i \le 200$$$) - 陷阱的参数(您必须严格在进入该房间后 $$$s_i$$$ 秒过去之前离开房间 $$$d_i$$$ )。多个陷阱可能会占据一个房间($$$d_i$$$ 的值可以重复)。
输出
对于每个测试用例,打印 $$$k$$$ 的最大值,该最大值允许您前往房间 $$$k$$$ 并返回房间 $$$1$$$ 而不会遇到活动陷阱。
示例
输入 #1
7 1 2 2 3 2 8 4 3 5 2 1 200 200 4 1 20 5 9 3 179 100 1 2 10 1 1 18 2 1 1 1 2 3 1 3 1 1 1 3
输出 #1
2 5 299 9 9 1 1
注意
第一个测试用例在上面的问题陈述中进行了解释。
在第二个测试用例中,第二个陷阱阻止您实现 $$$k\ge6$$$。如果$$$k\ge6$$$,第二个陷阱将在$$$3+s_2=3+3=6$$$时刻激活(你进入房间$$$4$$$加上$$$s_2$$$的时间)。如果是$$$k\ge6$$$,您将在$$$7$$$或更晚的时间返回$$$4$$$房间。那时陷阱将被激活。可以证明,可以在不遇到活动陷阱的情况下到达房间 $$$k=5$$$。
在第三个测试用例中,您可以到达房间$$$299$$$,然后立即返回房间$$$1$$$。