Mock CCO '18 Contest 4 Problem 5 - Spawn More Overlords

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 0.25s
Memory limit: 64M

Problem type

Richard has built a very large Zerg army. He has N different types of units in his army, specifically he has U_i units that each provide S_i units of supply.

Due to a supply crunch, he must give away some of his units. He wishes to free up exactly T units of supply. He can do this by sacrificing some of his existing units and spawning other units. He wants to minimize the sum of number of units he has to sacrifice and number of units he has to spawn. Help him!

Constraints

1 \le N \le 100

1 \le T \le 10^4

1 \le S_i \le 120

1 \le U_i \le 10^4

All S_i are unique.

Input Specification

The first line will contain two space-separated integers, N and T.

The next line contains N space-separated integers, the S_i values in order.

The next line contains N space-separated integers, the U_i values in order.

Output Specification

Output the minimum desired sum. Output -1 if it's impossible to lose exactly T units of supply.

Sample Input

3 70
5 25 50
5 2 1

Sample Output

3

Comments

There are no comments at the moment.