vouchers

Problem Description

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?

Limits

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.

Input

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.

Output

A single integer, the minimum amount of money Rar the Cat needs to pay to get all the cat food.

Sample Testcase 1

This testcase is valid for subtasks 1, 2, 3.

Input

5
1 2 3 4 5
1 1 1 1 1

Output

6

Explanation

You can buy the first three boxes of cat food and exchange the two vouchers obtained for the last two boxes of cat food.

Sample Testcase 2

This testcase is valid for subtasks 2, 3.

Input

5
1 10 3 15 8
2 3 3 2 2

Output

4

Explanation

You can buy the first and third boxes of cat food.


Submitting .cpp to 'vouchers'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 0.5 Seconds
Memory Limit: 1024MB
No. of ACs: 12
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 23
2 77
3 0