解题思路

本题是一个变形的背包问题：每个包裹可以选择两种“花费”（燃料），其中一种会额外消耗 1 张通行证。目标是先最大化派送包裹数，在此基础上最小化燃料消耗，并满足燃料 ≤ X、通行证 ≤ Y。

算法：动态规划（DP，二元约束下的最优化-可行性分离）

• 设计状态： 设 dp[j][k] 表示在处理若干包裹后，恰好派送 j 个包裹、使用 k 张通行证时的最小燃料。 初始化：dp[0][0] = 0，其余为正无穷。
• 转移（对每个包裹的常规/虫洞两种选择）：

题目内容

星际快递公司有 $N$ 个包裹需要派送，每个包裹有两种派送方式!

1、常规派送(消耗较多燃料)

2、虫洞派送(使用一个虫洞通行证，可以以消耗较少燃料的情况下完成派送)

当前快递飞船携带了 $X$ 单位的燃料和 $Y$ 张虫洞通行证。

星际快递公司想要计算，在优先派送尽可能多包裹的情况下，最小的燃料消耗是多少，请你帮助他们计算一下。

输入描述

第一行三个整数 $N,X,Y$ ，分别表示包裹数量，携带燃料量以及通行证数量。

接下来 $N$ 行，每行两个整数，表示各个包裹常规派送和虫洞派送分别需要的燃料量

$1≤N≤100,1≤X≤5000,1≤Y<50$ ，每个包裹常规派送和虫洞派送的燃料消耗均介于 $[1,50]$ 之间

输出描述

一行，两个整数，空格分开，表示最多可派送的包裹数量及对应的最小燃料消耗。

样例1

输入

3 20 1
8 5
7 4
10 6

输出

2 12

样例2

输入

4 25 2
10 6
8 5
12 7
9 6

输出

3 20