CADYDIST  Candy Distribution
Alice is a teacher that loves her students. As the school year reaches its end, she wants to reward all her students with candies for all their hard work.
Since each of her classes is unique, she decided she’ll give a different kind of candy for each class, and in order to avoid students being mad at others in their class, she wants to make things fair by giving all students in the same class the same kind of candy.
Happily, she went to the candy shop, and fortunately found out that it had N different types of candy, exactly the same number of classes of students she taught!
Looking at the prices and paying close attention to the number of students in each class, Alice noted that she could save some money by assigning the types of candy to certain classes. Because she’s a teacher, her income is not that big and saving money is very important to her, so she asked you to write a program to determine the least amount of money she must spend.
Input
Each test case consists of three lines. The first line contains a positive integer N (1≤N≤100000). The second line contains N integers C_{i}, the i^{th} integer indicates the number of students in Alice’s ith class. The third and last line also contains N integers P_{i} the i^{th} integer indicates the price of the i^{th} type of candy (1 ≤ C_{i}, P_{i} ≤ 100000).
The input ends with a line consisting of a 0, which indicates end of input.
Output
For each test case, output a line containing the least amount of money Alice must spend.
Example
Input: 4
1 1 1 1
2 2 2 2
5
10 80 37 22 109
6 8 8 20 15
0 Output: 8
2120
Added by:  Paulo Costa 
Date:  20120119 
Time limit:  0.301s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All 
Resource:  ITA  Brazilian ICPC Training Camp, JanFeb/2012 
hide comments
vishrut mishra:
20150817 21:07:42
use everything as a long long int, it'll save you a lot of WAs. 

fool_01:
20150817 15:41:33
For TLE, use printf,scanf . For wrong ans check overflows 

Liquid_Science:
20150805 16:04:18
got accepted after using long instead of int


xyz:
20150709 13:02:37
use unsigned long long int...


SangKuan:
20150704 02:21:38
greedy algorithm.and use quicksort or mergesort,do not use Selection sort or insert sort,it is O(n^2).and can use auto sorted struct,like priority_queue Last edit: 20150704 03:50:06 

Bhuvnesh Jain:
20150625 22:01:40
similar to problem FASHION


sujit yadav:
20150623 16:07:35
greedy !! :) 

hrishabh:
20150618 18:53:26
Simply use sort inbuild fx...


venkatesh:
20150617 07:27:04
In Python TLE, but in C++ AC : same logic 

Dushyant Singh:
20150608 08:23:06
Selection sort gives TLE! :( 