F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister 捐赠本站
Notice:开心刷题:)
Problem 1148. -- [CTSC2007]挂缀pendant -- 衡阳八中OJ离线版-2014-11-04

1148: [CTSC2007]挂缀pendant

Time Limit: 40 Sec  Memory Limit: 162 MB
Submit: 360  Solved: 161
[Submit][Status]

Description

“珠缀花蕊,人间几多酸泪”…… 挂缀在很早就被人们作为一种装饰品,垂坠的风韵,华丽摇曳的摆动,展现出一种与众不同的优雅与高贵。而我们的主人公小Q,正想买一条漂亮的挂缀放在寝室里作为装饰。挂坠的构成,是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成:分别是珠子、珠子上方的连接环与珠子下方的挂钩(如下图)。我们可以简单的认为从上往下数的第i个缀珠是将它的连接环套在其上方(也就是第i-1个)缀珠的挂钩之上(第一个除外)。小Q想买一根足够长的挂缀,这样显得更有韵味 然而商店的老板告诉小Q,挂缀是不可能做到任意长的,因为每一个珠子都受到重力作用,对其上方的挂钩有一定的拉力,而挂钩的承受能力是有限的。老板还告诉小Q,他一共拥有N个珠缀(假设每一个珠缀都很漂亮,小Q都很喜欢),每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的,当且仅当对于其上的每一个珠缀,它下方所有珠缀的重量和(不包含自身)不超过其挂钩的承受能力。小Q希望她的挂缀尽量长,你能帮她计算出最长可能的稳定挂缀么?当然,如果有多个可选方案,小Q希望总重量最小的。

Input

第一行包含一个正整数N,表示商店拥有的珠缀数目。接下来N行,每行两个整数(Ci , Wi),分别表示第i个珠缀的承受能力与重量。

Output

包行两行。第一行包含一个整数L,表示可以找到的最长稳定挂缀长度。第二行包含一个整数W,表示可以找到的长度为L的稳定挂缀中的最小重量和。

Sample Input

4
3 5
5 1
3 2
4 6

Sample Output

3
8

HINT

每一个测试点单独评分,对于每一个测试点:如果挂缀长度L与答案一致,且最小重量和W也正确,则得10分。如果挂缀长度L与答案一致,而最小重量和W与答案不一致,该测试点则得4分。否则得0分。

Source

[Submit][Status]

HOME Back