Sphere Online Judge

SPOJ Problem Set (classical)

10442. Candy Distribution

Problem code: CADYDIST


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 Ci, the ith integer indicates the number of students in Alice’s i-th class. The third and last line also contains N integers Pi the ith integer indicates the price of the ith type of candy (1 ≤ Ci, Pi  ≤ 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:2012-01-19
Time limit:2s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:ITA - Brazilian ICPC Training Camp, Jan-Feb/2012

hide comments
2014-08-25 20:12:42 Shaktiman
just keep attention on data types you are taking and their i/o
as for unsigned long long use %llu in scanf and printf
2014-06-12 06:15:21 Warrior Within !!!
used same logic...
tle with cin and accepted with scanf
2014-05-31 18:06:02 Ashish Gaurav
WA with long long, and AC with unsigned long long. I don't know how guys did it with plain long long.
2014-05-30 20:28:07 vijay kumar
RE(NZEC) with python3.2.3...gonna do the same in c...

My c++ code runs fine in Ideone but here it is RE(sigsegv)...!!!

AC...!!!

Last edit: 2014-06-30 21:36:13
2014-05-16 11:02:06 aman
AC in 2nd submission
2014-04-29 11:46:43 SHIVAM DIXIT
accepted with unsigned long long...wa with int
2014-01-09 15:22:23 californiagurl
how big is are the arrays?
2014-01-03 13:19:14 pika_pika
use long long for all variables... don't know why such constraints were used. ?? :/
2013-12-18 14:43:51 aura
i hate my silly mistakes.
2013-12-17 05:28:35 kv
use long long int and printf,scanf... :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.