← 返回题目列表

AtCoder · icpc2016autumn_f

F. 逃离地狱

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

问题陈述

有一天,佛陀往地狱里一看,发现了一位上班族。他做坏事,比如强迫下属努力工作。然而,他一生只做了一件好事。他为了拯救下属的生命而拒绝了顾客的无理要求。 佛陀认为,作为善行的回报,办公室职员应该有机会逃离地狱。佛陀取了一根蜘蛛丝,放下到地狱。

上班族拿着蜘蛛丝爬了上去,但距离$L$米太长,有一天无法逃脱。他喝了 $N$ 能量饮料,并且每天喝一杯。在他喝第 $i$ 能量饮料的那天,他可以在白天爬 $A_{i}$ 米,然后在夜间滑下 $B_{i}$ 米。如果白天能到达大于或等于$L$米的高度,他就可以逃走,而不会滑落。 $N$ 天后,丝绸将被切断。

他意识到其他罪人在夜间爬上了丝绸。他们在第 $i$ 晚爬升了 $C_{i}$ 米,而白天却没有滑落。如果追上上班族,他们应该会发生冲突,丝被切断。因此,他需要在其他罪人抓住他之前逃跑。 你的任务是编写一个程序,计算能量饮料的最佳顺序,并输出他最早可以逃脱的日期。如果他无法逃脱,你的程序应该输出$-1$。


输入

输入由单个测试用例组成。

$N$ $L$
$A_1$ $B_1$
...
$A_N$ $B_N$
$C_1$
...
$C_N$

第一行包含两个整数$N$($1 \le N \le 10^{5}$)和$L$($1 \le L \le 10^{9}$),分别表示能量饮料的数量和蜘蛛丝的长度。下面的$N$行显示了饮料的信息:其中第$i$个表示第$i$个能量饮料,他爬上$A_{i}$ ($1 \le A_{i} \le 10^{9}$)米并滑下$B_{i}$ ($1 \le B_{i} \le 10^{9}$)米。接下来的 $N$ 行显示了其他罪人爬了多远:其中第 $i$ 个包含整数 $C_{i}$ ($1 \le C_{i} \le 10^{9}$),这意味着他们在第 $i$ 天爬了 $C_{i}$ 米。

输出

打印他最早可以逃脱的日期。如果他无法逃脱,则打印 $-1$ 代替。



示例输入 1

3 9
6 3
5 2
3 1
2
2
2

样本输入 1 的输出

2

示例输入 2

5 20
3 2
4 2
6 3
8 4
10 5
4
2
3
4
5

样本输入 2 的输出

-1

示例输入 3

5 20
6 5
7 3
10 3
10 14
4 7
2
5
3
9
2

样本输入 3 的输出

3

示例输入 4

4 12
8 4
6 4
2 1
2 1
1
1
4
4

样本输入 4 的输出

-1