Rar the Cat is shopping for cat food to prepare for the Great Feline Feast.
There are N boxes of cat food in the supermarket, numbered from 1 to N. The ith box of cat food costs $ Ai.
Being a greedy cat, Rar the Cat wants to get all the cat food.
As the supermarket is having a sale today, there are N vouchers available, also numbered 1 to N. By buying the ith box of cat food, Rar the Cat will receive the ith voucher. Rar the Cat can exchange the ith voucher for at most Bi boxes of cat food at no cost.
What is the minimum amount of money Rar the Cat needs to pay to get all the cat food?
For all testcases, 1 ≤ N ≤ 5000, 0 ≤ Ai ≤ 109, 0 ≤ Bi ≤ 109 in addition to the limits below.
Subtask 1 (23%): Bi = 1.
Subtask 2 (77%): No further constraints.
Subtask 3 (0%): Sample Testcases.
The first line of input will contain one integer, N.
The following line will contain N integers, Ai.
The following line will contain N integers, Bi.
A single integer, the minimum amount of money Rar the Cat needs to pay to get all the cat food.
5 1 2 3 4 5 1 1 1 1 1
You can buy the first three boxes of cat food and exchange the two vouchers obtained for the last two boxes of cat food.
5 1 10 3 15 8 2 3 3 2 2
You can buy the first and third boxes of cat food.