Minimum Cost to Purchase Servers

Each machine can be bought at most once; its price is 1 or 2 and its power is an integer. Choose any set of machines whose total power is at least target and find the minimum total price. You may choose no machine at all; if no feasible set exists, return −1.

输入格式

The first line contains n target, the second line contains power, and the third line contains price. The original statement only restricts price to 1 or 2 and gives no other value bounds; on this site 1≤n≤200000, −10^9≤power[i]≤10^9, −10^14≤target≤2×10^14. Power is not arbitrarily required to be positive; machines with non-positive power are still valid input.

输出格式

Output a single integer, the answer.

样例 1

输入：

4 7
4 4 6 7
1 1 2 2

输出：

2

样例 2

输入：

3 5
-5 0 4
1 2 2

输出：

-1

样例 3

输入：

1 -1
-5
1

输出：

0

样例说明

The answers are 2, −1 and 0. In the last example the empty set has power 0, which is already not less than −1, so you cannot be forced to buy a machine.