Oven load: hints, no solution

A bakery oven can carry at most capacity kilograms per firing. Tray i weighs weights[i] kilograms and is worth values[i]. Each tray can be loaded at most once, and trays with the same weight and value are still separate trays. Choose a set of trays whose total weight is at most capacity so that their total value is as large as possible, and return that value. If no tray fits, the answer is 0.

Examples

Input

weights = [3, 4, 2], values = [30, 50, 15], capacity = 6

Output

65

Note

Trays of 4 kg and 2 kg are worth 50 + 15.

Input

weights = [2, 3], values = [9, 9], capacity = 1

Output

0

Note

Neither tray fits.

Input

weights = [6, 5, 5], values = [30, 20, 20], capacity = 10

Output

40

Note

Two 5 kg trays beat the single best-value-per-kilo tray.

Constraints

• 0 <= weights.length <= 200, and values has the same length
• 1 <= weights[i] <= 1000, 1 <= values[i] <= 1000
• 0 <= capacity <= 10000

Hint 1: a nudge

Take one tray. You either put it in the oven or you do not. What would you need to know about the remaining trays to compare those two choices?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing