DMOPC '14 Contest 5 P4 - Kittan's Dilemma - Olympiads Online Judge

DMOPC '14 Contest 5 P4 - Kittan's Dilemma

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

Kittan is in charge of the battleship-like Dai-Gunzan and therefore is responsible for choosing which Gunmen should stay on Dai-Gunzan's deck to patrol. Kittan has $N$ ~N~ possible Gunmen to choose from. Unfortunately, Kittan doesn't have the patience to carefully assess each individual Gunmen's capabilities, so he labels each as "Good" or "Bad", based on a cursory glance. He assigns a protection value of $2$ ~2~ to "Good" Gunmen and $1$ ~1~ to "Bad" Gunmen.

The deck of Dai-Gunzan has limited room — there are exactly $M$ ~M~ units of space for patrolling Gunmen to use. Kittan is a busy man, so he assigned Jorgun to keep track of the amount of space each Gunmen takes up. He also assigned Balinbow to figure out the maximum sum of protection values Dai-Gunzan can have by taking a subset of available Gunmen whose total space consumption does not exceed $M$ ~M~. Unfortunately, while Jorgun is barely smart enough to measure Gunmen, Balinbow desperately needs your help in this optimization problem.

Input Specification

The first line of input will contain two integers $N$ ~N~ and $M$ ~M~, separated by a single space.

The next $N$ ~N~ lines of input will contain two integers $S_i$ ~S_i~ and $P_i$ ~P_i~, the space and protection value of the $i^{th}$ ~i^{th}~ Gunmen, respectively.

Output Specification

The first and only line of output should be the maximum protection value Dai-Gunzan can have.

Constraints

For all subtasks:

$1 \le P_i \le 2$ ~1 \le P_i \le 2~

Subtask 1 [25%]

$1 \le N, M, S_i \le 1\,000$ ~1 \le N, M, S_i \le 1\,000~

Subtask 2 [75%]

$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~

$1 \le M, S_i \le 10^9$ ~1 \le M, S_i \le 10^9~

Sample Input

Sample Output

Explanation

Take the Gunmen that use 1, 4, and 5 space for a total protection value of $1+2+2=5$ ~1+2+2=5~.

Comments

1

illuminati commented on March 17, 2015, 2:16 a.m.

I got quickscoped Barred from entering a solution :/ kek

1
FatalEagle commented on March 17, 2015, 2:31 a.m. ← edited →
https://dmoj.ca/tos/

if (prot == 4) prot = 5;

0

illuminati commented on March 17, 2015, 2:48 a.m.

LOL thanks, i noticed that in my submission. Didn't read the TOS and decided to be cheap, sorry about that. I don't know why my program didn't work for that one case..

2

FatalEagle commented on March 17, 2015, 3:10 a.m.

I've deleted the offending submission. Don't do it again. Instead, figure out why your program doesn't work, fix it, and resubmit.

0

pyrexshorts commented on March 13, 2015, 1:14 a.m.

I'm stuck on this question.

Mod Edit: Do not post full solutions or algorithms in the comments.

1

fifiman commented on March 13, 2015, 3:00 a.m.

Idea : Try seperating the "good" gunmen and the "bad" ones

1

kobortor commented on March 10, 2015, 10:18 p.m.

For N, M and S

1

awaykened commented on March 10, 2015, 10:19 p.m.

Subtask 1 [25%]

1≤N,M,Si≤1000

Subtask 2 [75%]

1≤N,M,Si≤100000

For all subtasks, 1≤Pi≤2.

0

kobortor commented on March 10, 2015, 10:21 p.m.

Does subtasks 2 include subtask 1?

0

FatalEagle commented on March 10, 2015, 10:43 p.m.

Subtasks are disjoint, but they may share test cases. It all adds up to 100%.