Problem Description

Takahashi and Aoki are conducting a transaction. Initially, Takahashi has 0 yen.

Takahashi has N treasures numbered from 1 to N. Selling treasure i to Aoki will earn him x_i yen.

Aoki is selling N items numbered from 1 to N. Item i has a value of v_i and is sold for c_i yen.

The transaction proceeds as follows:

1. Takahashi decides whether to sell a treasure or buy an item. If he chooses to sell, proceed to step 2. If he chooses to buy, proceed to step 3.
2. Takahashi sells the treasure with the smallest number to Aoki and receives money. Then, Aoki chooses one item to stop selling. Return to step 1.
3. Takahashi buys 0 or more items that are still for sale and ends the transaction. Takahashi cannot buy items that would make his money go below 0 yen.

The score is the total value of the items Takahashi purchased.

Takahashi aims to maximize the score, while Aoki aims to minimize the score. What will the score be?

Input Format

The input is given from the standard input in the following format:

$ N $ $ x_{1} $ $ ... $ $ x_{N} $ $ c_{1} $ $ ... $ $ c_{N} $ $ v_{1} $ $ ... $ $ v_{N} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
200 1000 1
100 100 300
1000 2000 1000000

Sample Output #1

1000

Sample Input #2

2
1 100
1 100
100 1

Sample Output #2

0

Sample Input #3

5
100 1 1 1 1
1 1 1 1 1
1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000

Sample Output #3

4000000000000000

Sample Input #4

18
89 36 77 25 84 49 67 21 78 94 55 50 22 40 44 17 93 11
55 81 89 38 19 65 68 75 66 52 75 93 94 31 73 86 25 79
38 81 44 33 70 20 89 34 13 45 27 88 91 85 36 98 52 93

Sample Output #4

337

Notes/Hints

Constraints

• $1 \leq N \leq 18$
• $1 \leq x_i, c_i, v_i \leq 10^{15}$
• All given inputs are integers

Sample Explanation 1

• An example of the movement of the two players is described below:
  1. Takahashi chooses to sell a treasure, sells treasure 1, and gains 200 yen.
  2. Aoki stops selling item 2.
  3. Takahashi chooses to sell a treasure, sells treasure 2, and gains 1000 yen.
  4. Aoki stops selling item 3.
  5. Takahashi chooses to buy items, buys item 1, and ends the transaction.

Sample Explanation 2

• No matter how Takahashi acts, he cannot purchase any items.

见题面 Input 部分

见题面 Output 部分