All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

The Chocolate Boy
/
No tags
Problem
Editorial
Analytics

One day Jenish goes to a chocolate shop to buy chocolates. There are \(N\) chocolates, where the \(i^{th}\) chocolate has a sweetness \(sweet[i]\) .He only buys chocolates of type soft(he doesn't like hard chocolates). But he wants to buy chocolates such that sum of sweetness does not exceed \(M\). He has one special energy. Using it, he can halve the sweetness of any chocolate present in a shop. He can use this energy at most one time. You have to find the maximum price he has to pay. 

INPUT:

The first line contains \(N\) - the total number of chocolates in a shop & \(M\) - the limit for sweetness.

The next \(N\) contains - the name of chocolate, type of chocolate ('H' for hard & 'S' for soft), the sweetness of the chocolate, the price of chocolate. 

OUTPUT:

You have to print the maximum price Jenish has to pay.

CONSTRAINTS:

\(1 \le N \le 1000\)

\(1 \le M \le 1000\)

\(1 \le sweet[i] \le 1000\)

\(1 \le price[i] \le 10^6\)

SAMPLE INPUT
4 4
dairymilk S 5 15
kitkat H 7 10
fivestar S 2 20
snickers S 4 17

SAMPLE OUTPUT
37
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?