Pizza Delivery

Chef Jami had recently started home delivery service for pizzas. Jami has only a single delivery boy that delivers the order by riding his bicycle. Today Chef Jami received $N$ pizza order, the house of the person that ordered the $i$-th pizza needs $A_i$ unit time to prepare and the order is $B_i$ km away from the restaurant. The delivery boy cannot deliver more than one order at a time and takes 1 unit time per km. Therefore, after delivering an order, he must return back to the restaurant to take the next order. It takes the delivery man no time to get back to the restaurant and the Chef can continue cooking without waiting for the delivery man to come for the next order.

The delivery boy is a lazy person and does not want to spend much time in the delivery process, so he wants your help in prioritizing the orders so that he can deliver all orders in least amount of time.

Input

First line contain the number of orders $N$ ($1 ≤ N ≤ 500$).

Second line contains $N$ space separated integers $A_i$ ($1 ≤ A_i ≤ 1000$) - the packing time of every pizza by Chef Jami and the third line contains $N$ space separated integers $B_i$ ($1 ≤ B_i ≤ 1000$) - the distance of the house from the restaurant.

Output

Print the least amount of time to deliver all the orders.

Samples

Input	Output
4 1 1 30 5 5 30 5 10	51

Input	Output
6 11 9 16 19 15 17 11 23 9 7 11 6	93