题目描述
拼装店有 种配件,第 种每件重 ,且每人限购 件。你想购买若干配件(每种 0 到 件),使总重量恰好为 。判断这个目标是否可行:可行输出 YES,否则输出 NO。
输入格式
第一行两个整数 和 ,表示配件种数与目标总重。接下来 行,每行两个整数 和 ,分别表示第 种配件的单件重量与限购件数。
输出格式
一行,YES 或 NO。
样例
输入
3 10 5 1 3 2 4 1
输出
YES
数据范围
- 对于 30% 的数据: 20, 1000,且保证所有 = 1(退化为 01 背包可达性)。
- 对于 60% 的数据: 50, 5000, 3(可爆搜每种买几件)。
- 对于 100% 的数据: 100, , 50,1 ,。