绅士神犇面前有一个边缘摆了n个蛋糕的圆桌。每个蛋糕的饱腹值为a_i、奶油含量为b_i。作为绅士,神犇一定不会跳过某个蛋糕去吃下一个;他不喜欢奶油太多的蛋糕,但绅士也要吃饱肚子,即所吃的蛋糕的饱腹值之和大于等于s。
现在,绅士的睿智决定了神犇要提前知道吃饱的前提下,他所吃的蛋糕里奶油含量最高的那块的奶油含量最少是多少,这样他就有充分的心理准备从容应对而不会在吃蛋糕时表现的不足够优雅。
第一行,两个整数分别为n,s。
第二行,n个a_i,依次表示每块蛋糕的饱腹值。
第三行,n个b_i,依次表示每块蛋糕的奶油含量。
对于100%的数据:
1\le n \le 2×10^5;
1\le s \le 10^9;
1\le a_i,b_i \le 10^9。
若绅士神犇无法吃饱,输出-1;否则,输出他吃饱的前提下,他所吃的蛋糕里奶油含量最高的那块的奶油含量最少是多少。
5 9 4 3 7 6 1 1 3 9 2 5
5
不吃7、9的那块,饱腹值为14,奶油含量最高的一块为5。
时间限制 | 1000 毫秒 |
内存限制 | 128 MB |