问题1104--小W逃跑

1104: 小W逃跑

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

提交

题目描述

    糟糕的事情发生了,小W开始逃跑了。
    由于这个月小W有好多事情要干,今天已经26号了,因此这道题差点出不完了。
    可爱的小W决定战略性放弃一些事情,并且把耗时较长的任务重新规划时间,抹掉零头时间以提高效率,从而获得新的计划。
    目前小W手头的任务可以分为两类。

    1. 耗时较短:这一类任务目前计划的消耗时间范围在[0,25-1],这类任务小W觉得没有办法再提高效率了。
    2. 耗时较长:这一类任务目前计划的消耗时间范围在[210,215-1],这类任务小W觉得可以把提高效率,把零头抹掉。

    这段是废话:昨天,小W上街买了一块牛排作为夜宵,报价121。由于小W次吃夜宵消耗的金钱都在[100, 1000-1]范围内,加上小W太有钱了可以忽略花钱的细节,因此每次记账都会抹零。因此昨天的夜宵记作100元。

    对于任务的时间规划,结合小W的程序员身份,决定抹掉任意第2类任务计划消耗时间的二进制表示的最后10个0,从而使得新的计划中,消耗时间变短。例如,对于某一个目前计划耗时1025的任务,二进制表示为10000000001,抹掉最后10个0后,表示为10000000000,新的计划耗时1024。
    每个任务会给小W带来一定的愉悦度,小W想要知道,花费不超过C单位时间,新的计划下,最多能获得多少愉悦度呢?(即执行完成的任务的愉悦值之和最大)

输入

第一行输入1 ≤ n  1000,1  32767000
接下来有n行,表示n个任务,其中第i行有两个整数ci ∈ [0, 25-1] ∪ [210,215-1], 1 ≤ wi  ≤ 1e5,其中ci表示第i个任务在原计划中的耗时,wi表示第i个任务给小W带来的愉悦值。

输出

一行一个整数,表示小W在新的计划下,能够获得的最大的愉悦值。

样例输入 Copy

3 1025
1025 1
1026 2
1 3

样例输出 Copy

5

提示

第一个任务在新的计划中需要1024单位时间,第二个任务也需要1024单位时间,第三个任务需要1单位时间。因此小W决定执行任务2和任务3,刚好用了1025单位时间,获得5点愉悦值。

来源/分类