Anyone can make this code

[ninjago]

The running time of the

program should be less than 4 seconds.

Mina wants to go on a trip during the a summer vacation.

She has to pay in advance several things such as airfare, lodging, car rent, show tickets,

etc. To pay them, she wants to use her mileage points from her credit card, airline, cell

phone, etc.

She can divide mileage points from one source (ex. airline mileage) to pay multiple things

(ex. airfare and tickets). Also she can merge mileage points from multiple sources (ex.

airline and cell phone) to pay one thing (ex. car rent).

However, there can be a limitation in applying certain mileages to certain type of payments.

For example, suppose she has 100,000 (in Korean Won) airline mileage and 50,000 cell phone

mileage, and she wants to pay 90,000 for airfare and 70,000 for car rent 1

, there can be a

limitation that she can use airline mileage for both airfare and car rent, but she only can

use cell phone mileage for car rent.

With that limitation, it is not a good idea to use only airline mileage to pay for car rent,

because, after that, she needs to pay 60,000 for car rent (after she use 90,000 for airfare

and 10,000 for car rent from 100,000 airline mileage). Instead, it is a reasonable choice to

use 50,000 cell phone mileage for car rent first, and then use 100,000 airline mileage for

airfare and car rent, which results her to pay 10,000 for either car rent or airfare.

Now given a set of mileages, a set of payments, and lists of feasible payments for each

mileage, calculate the minimum amount of money that Mina has to pay.

Input

2 <-- # of mileages

10 5 <-- mileage #0 and #1

2 <-- # of payments

9 7 <-- payment #0 and #1

0 1 <-- mileage #0 can be used for payment #0 and #1

1 <-- mileage #1 can be used for #1

Output

1 <-- minimum of payment 1 is needed

[kbw]

We can only help, we can't do the work for you.