#CW27. 层塔陈列(towers)
层塔陈列(towers)
题目描述
小 W 要用仓库中的展品搭建至多 座陈列塔。仓库里有 种重量不同的展品,第 种展品的重量为 ,共有 个;所有 两两不同。
一座塔由若干展品从下到上叠放,可以只含一个展品。为了保持稳定,塔中任意两个相邻展品都要满足“下方展品的重量 上方展品的重量 ”。
每个展品最多使用一次,也可以不使用。不同塔之间没有额外限制。
请计算这些塔最多能使用多少个展品。
输入格式
第一行输入三个整数 。
接下来 行,第 行输入两个整数 ,表示一种展品的重量和数量。
输出格式
输出一个整数,表示最多可以使用的展品数量。
样例 1 输入
4 2 4
1 2
4 1
6 2
10 1
样例 1 输出
5
样例 1 解释
可以搭建重量序列分别为 和 的两座塔,共使用 个展品。每个序列都按从下到上的顺序书写。
样例 2 输入
5 3 3
2 4
3 2
5 1
8 5
12 2
样例 2 输出
9
数据范围
对于所有测试数据,保证:
- ;
- ;
- 所有 两两不同。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | 且 | |
| B | 15 | 且 | |
| C | 20 | ||
| D | 25 | ||
| E | 30 | 无额外限制 |