High School Programming League Problems Archive

A chain of supermarkets is trying to attract more customers by awarding points for purchased goods, and points can later be exchanged for gifts. Joan likes gifts (and as a matter of fact likes shopping as well), so she decided to do her shoppings in one of the stores of the chain. Since the number of free gifts depends on the number of points Joan collects, she is planning to buy all the goods she needs in such a way that the number of points she collects is the maximum possible.

Write a program that, given the maximum amount of money Joan intends to spend, the goods she needs, and the resources the store can provide, calculates how many points she can collect while shopping.

Input

The first line contains the maximum amount of money Joan intends to spend (integer 0 < X <= 10¹²) and the number of types of goods that are available in the shop (1 <= n <= 10⁶).

The second line contains a sequence of nonnegative integers 0 <= x_i <= 10⁶ (1 <= i <= n), describing the number of goods of type i which Joan has to buy.

The third line contains a sequence of nonnegative integers x_i <= y_i <= 10⁶ (1 <= i <= n) - the number of goods of type i which are available in the shop.

The fourth line contains the sequence of positive integers 0 < c_i <= 10⁶ (1 <= i <= n) - the price of one piece of goods of type i.

The last line contains a sequence of nonnegative integers 0 <= p_i <= 10⁶ (1 <= i <= n) - the number of points that Joan gets for buying one piece of goods of type i.

All numbers in the above sequences are separated by spaces. You can assume that Joan has enough money to buy all goods she needs (x₁*c₁ + ... + x_n*c_n <= X).

Output

Output Joan's shopping, i.e. a sequence of nonnegative integers z_i (1 <= i <= n) - the number of goods of type i bought by Joan. The solution is considered correct if and only if:

• x_i <= z_i <= y_i,
• z₁*c₁ + ... + z_n*c_n <= X.

Example 1

Input:
10 1
1
2
5
5

Output:
2

Score:
10

Example 2

Input:
10 2
1 1
2 2
6 4
1 2

Output:
1 1

Score:
3

Points

The score awarded to your program is the the total number of points you collected while shopping (in all the individual test cases). Your answer must be correct for all test cases.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Notes

• For the first four weeks of the series (till noon Saturday, October 18) all submissions to this problem will be visible to all users and tested on 5 data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on all 10 data sets. (Earlier solutions will also be extended to all 10 data sets)
• The data sets used for testing will be made available after the end of the series on request; for your information, the SHA1 checksums of all 10 input files are as follows:
  2538c7cc348490e993779cbbc6d2b89a87100b2e fcec7b106ba3cd1c28530e0619baeaeb66beb0e8 bf1cb329fe150f7995742cbccf0ee0f6535f1ef5 508c58cae420407a39604f9830a2d20d463f7b53 1e490f027d0646b4e1e2567fd6f22a7581128974 58783c61dee71eb7ce47d81828b79b5f90a4ade3 11fefe72ab1af70a4c5e99df93d13aa351cba092 12e672604063f02cbf6509db45880bfe1b89c1d8 2172c50799ff2270931e9ab32c8bf5d07d4b40a4 6caad45aa547baa8d8c40de5c77b680cf7014786