#6729. 300颗够吗

300颗够吗

题目背景

百江最近迷上了生存建造题材,在他游玩一款非常经典的生存建造题材的泰拉瑞亚的时候刷到了一个梗叫做300颗够吗。于是他根据这个梗想出来一道需要用C++来解决的题目:

题目描述

游戏中有 nn 个 Boss。击败第 ii 个 Boss 可以获得 bib_i 个金币。Boss 不需要按顺序击败,但每个 Boss 只能被击败一次。

然而要击败 Boss 前就要花钱购买弹药。根据速通大神的精密计算,击败第 ii 个 Boss 需要花费 aia_i 个金币来购买子弹。

百江想要知道,如果初始持有 mm 个金币,能否击败所有的 Boss?

输入格式

每个测试文件均包含多组测试数据。

  • 第一行输入一个正整数 TT,表示测试数据的组数;
  • 接下来每组测试数据:
    • 第一行包含两个正整数 n,mn, m
    • 接下来 nn 行,每行两个整数 ai,bia_i, b_i,表示需要花费 aia_i 个金币击败第 ii 个 Boss,然后获得 bib_i 个金币。

输出格式

对于每组测试数据输出一行,如果能击败所有 Boss 输出 Yes,否则输出 No

3
6 3
2 5
3 3
5 5
5 3
4 2
5 4
4 4
2 3
5 5
3 3
2 3
6 2
2 5
3 3
5 3
1 3
4 2
4 4
No
Yes
Yes

数据范围

测试点 TT \le nn \le mm \le ai,bia_i, b_i \le
1~2 10 9 10510^5
3~4 20 10310^3
5~6 5 10510^5 10310^3
7~8 500 10310^3 10510^5
9~10 8 5000

对于 100%100\% 的数据,保证:

  • 1n5×1051 \le \sum n \le 5 \times 10^5
  • 1m1051 \le m \le 10^5
  • 0ai,bi1050 \le a_i, b_i \le 10^5