CF1846A Rudolph and Cut the Rope
题目描述
#### 题目大意
现在有 $n$ 个钉子被钉在墙上,第 $i$ 个钉子离地 $a_i$ 米。每个钉子都被一根长度为 $b_i$ 绳子的一端所连接。所有钉子一个接一个地被钉在不同的高度。一个糖果被一次性系在所有的绳子上,它被系在绳子不与钉子相连的那一端。
为了拿到那颗糖果,你需要将他放到地面上。为了做这件事, $Rudolph$ 可以一次一条地剪断一些绳子。帮助 $Rudolph$ 找到获得糖果需要剪断的绳子数量的最小值。
以下图像展示的是第一组样例。
输入格式
第一行包括一个数字 $t~(1 \le t \le 10^4)$ —— 测试用例的数量
每个测试用例的第一行为一个数字 $n ~(1 \le n \le 50)$ —— 钉子的数量
接下来 $n$ 中的第 $i$ 行每行包含两个数字 $a_i$ 和 $b_i$ $(1 \le a_i,b_i \le 200)$ —— 第 $i$个钉子的高度和连接在它上面的绳子长度,每个 $a_i$ 是不同的。
保证所有数据都不会相互矛盾,并且可以构建题目中所描述的构造,
输出格式
对每个测试样例输出一个数字 —— 让糖果落到地面所需要剪断的绳子数量的最小值。