← 返回题目列表

Codeforces · 1533/A

A. 前往伯敦

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

维卡决定去伯敦旅行。她在 $$$k$$$ 那天来到伯敦。 Vika 不想花钱住酒店,幸运的是她有 $$$n$$$ 朋友住在 Bertown,允许 Vika 住在他们的房子里。第 $$$i$$$ 个朋友告诉 Vika,她可以从第 $$$l_i$$$ 天到第 $$$r_i$$$ 天(含)住在他们家。

Vika 决定只住在一个朋友家里。帮助维卡确定她可以在伯敦停留的最长天数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 100$$$) — Vika 的朋友数量以及 Vika 来到 Bertown 的日期。

然后是 $$$n$$$ 行,每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 100$$$) 表示 Vika 可以在第 $$$i$$$ 位朋友家里住宿的时间。

输出

对于每个测试用例,输出一个整数 - Vika 可以在 Bertown 停留的最大天数(或者 $$$0$$$,如果 Vika 的朋友都不能在 $$$k$$$ 天接待她)。

示例

输入 #1

3
3 3
1 4
2 6
4 10
2 4
2 3
5 8
2 4
4 4
1 3

输出 #1

4
0
1

注意

在第一个示例中,Vika 可以从第 $$$3$$$ 天到第 $$$6$$$ 天住在第 $$$2$$$ 朋友家里。

在第二个示例中,Vika 的朋友都无法在第 $$$4$$$ 天接待她。

在第三个示例中,Vika 可以住在第 $$$1$$$ 个朋友家里,但仅限第 $$$4$$$ 天。