Basic Knapsack

Basic Knapsack

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

为了给自己选举大队长造势,断罪小学三年6班的李子明同学决定给他身边的同学发放旺仔牛奶,在同学之间拉拢人气。
根据自己在大队内部的工作经验,李子明对三年级的每名同学做了一系列分析:他的潜在目标共有\(N\)人,如果给第\(i\)名学生赠送不少于\(t_i\)罐旺仔牛奶,那么该名同学就会为他拉拢\(c_i\)点人气,\(i=1,2 \cdots N\)。但李子明不想过早让他的父母知道自己贿选的事,所以他只能用自己的零花钱充当经费。由于经费有限,李子明只买得起\(T\)罐旺仔牛奶,而他也很可能得放弃一些潜在目标。为了让拉票的效率尽可能高,所以他打算用剩下的一点经费请你帮他编写一个程序,为他设计一个拉拢尽可能多人气值的方案。
不巧的是,在他买旺仔牛奶的时候,他自言自语的话被另一个大队长候选人偷偷录了下来,所以李子明不得不把原本用来买旺仔牛奶的钱用在了危机公关上,请人写程序的钱就更不存在了。请你计算一下,如果“录音门” 没有发生,那么李子明最多可以用这\(T\)罐旺仔牛奶拉拢到多少人气值?有多少种方案使得他拉拢到的人气值最高?
这里“不同方案”的严格定义是:对于两种方案,若存在某个人,他在且只在其中一种方案里边,那么就说这两种方案是不同的。

I/O格式

输入

第一行是两个正整数\(N, T\);
之后\(N\)行分别描述\(N\)名同学的信息,每行两个正整数\(t_i, c_i\),含义见上。

输出

在一行内输出两个正整数\(C_{max}, K\),分别表示最大人气值,以及得到最大人气值的方案。输出时两个整数用一个空格隔开。

样例

输入

3 5
2 6
3 7
4 13

输出

13 2

数据规模及约定

\(N \le 300, \quad T \le 3 \times 10^4, \quad t_i \le T, \quad c_i \le 10^6, \quad K \le 10^6\)
70%的数据满足:\(K = 1\)
时间限制1s,空间限制256MB。

2019.1.30补题通道

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2019-01-30 17:30
结束于
2019-02-10 00:00
持续时间
246.5 小时
主持人
参赛人数
25