mehta-and-the-bank-robbery

One fine day, when everything was going good, Mehta was fired from his job and had to leave all the work.
So, he decided to become a member of gangster squad and start his new career of robbing.
Being a novice, mehta was asked to perform a robbery task in which he was given a bag having a capacity W units.
So, when he reached the house to be robbed, there lay N items each having particular weight and particular profit associated with it.
But, theres a twist associated, He has first 10 primes with him, which he can use atmost once, if he picks any item x, then he can multiply his profit[x] with any of the first 10 primes and then put that item into his bag. Each prime can only be used with one particular item and one item can only have atmost one prime multiplied with its profit. Its not necessary to pick all the items. If he doesnt want to use a prime with any particular item, he can simply add the profit as it is, more specifically, 1*profit[x] for xth item will get added to its total profit, and that he can do with as many items as he wants. He cannot fill his bag more than weight W units. Each item should be picked with its whole weight, i.e it cannot be broken into several other items of lesser weight. So, now to impress his squad, he wishes to maximize the total profit he can achieve by robbing this wealthy house.

Input:

First Line of input containts two integers N and W.
Next N lines contain information of ith item, describing profit and weight of the ith item, profit and weight are separated by single space.

Output:

In a single line, output the maximum profit obtainable.

Constraints:

1 ≤ N ≤ 2000, 1 ≤ W ≤ 2000

1 ≤ Profit[i] ≤ 10^9, 1 ≤ Weight[i] ≤ 2000

Explanation:

As all, the items can be picked, so maximum profit is equal to = 1 X 19 + 2 X 23 + 3 X 29 = 152

SAMPLE INPUT
3 4
1 1
2 1
3 1

SAMPLE OUTPUT
152

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions: