问题陈述
有一天,佛陀往地狱里一看,发现了一位上班族。他做坏事,比如强迫下属努力工作。然而,他一生只做了一件好事。他为了拯救下属的生命而拒绝了顾客的无理要求。 佛陀认为,作为善行的回报,办公室职员应该有机会逃离地狱。佛陀取了一根蜘蛛丝,放下到地狱。
上班族拿着蜘蛛丝爬了上去,但距离$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