434. Chemists
Time limit per test: 0.75
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
The chemists had gathered to carry out an important experiment. That experiment required some tubes filled with liquid (each tube had to contain a certain amount of liquid). The experiment was set on 8 AM on the next day. They had worked hard, and there was the right amount of liquid in tubes by the end of the day. The chemists had decided to celebrate the occasion and, when morning came, they found out that someone had been pouring the liquid from and into the random tubes during the night. It is possible that this person had spilled the liquid or poured in an extra amount of it. Help the chemists to find out the minimum number of pourings to get the required amount of liquid in all tubes.
There are
N tubes with
S_{i} liters of liquid in
ith tube. It is allowed to pour any amount of liquid from any one tube to another. You have to get the right amount of liquid in each tube (
D_{i} for
ith tube) after the minimum number of pourings.
Input
The first line of input contains an integer number
N. The second line consists of
N integer numbers
S_{i} separated by space. The third line consists of
N integer numbers
D_{i} separated by space. 1 ≤
N ≤ 21, 1 ≤
S_{i},
D_{i} ≤ 1000.
Output
Output one number — the minimum number of pourings, or 1 if the pouring is impossible.
Example(s)
sample input

sample output

7
1 2 3 4 5 6 7
7 4 5 1 2 6 3

4
