Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Pizza Delivery

Limits: 1s, 256 MB

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 ith pizza needs Ai unit time to prepare and the order is Bi 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 Ai ( 1 ≤ Ai ≤ 1000 ) - the packing time of every pizza by Chef Jami and the third line contains N space separated integers Bi ( 1 ≤ Bi ≤ 1000 ) - the distance of the house from the restaurant.

Output

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

Samples

InputOutput
4
1 1 30 5
5 30 5 10
51

Author
Discussion
Submit

Login to submit