Limits 1s, 512 MB

Maybe you all are familiar with Jenga Game. "Jenga is played with 54 wooden blocks. Each block is three times as long as it is wide, and one fifth as thick as its length".

Today we are going to play another version of Jenga game. In our game we have two tower made of wooden blocks and they (wooden blocks) are of different heights. These wooden blocks sit on top of another thus creating a tower. Height of a tower is the summation of height of the blocks.

You will be given configurations of two towers (i.e. sequence of wooden blocks for each tower).

You are allowed to remove any amount (possibly 0) of blocks from any configuration.

Your task is to find the minimum number of blocks to be removed from the given two configuration of blocks to make the heights of two tower equal.

Input

The first line of the input consists of an integer value n , 0 < n <= 16 . (n, Number of wooden blocks to create first tower and second tower).

Second line contains n positive integers bi (0 < bi<108). bi is the height of ith block.

Third line contains n positive integers ci (0 < ci<108). ci is the height of ith block.

Output

Print a single integer R which denotes the minimum number of blocks to be removed from the given two configuration of blocks to make the heights of two tower equal.

Sample

InputOutput
3
1 5 9
2 6 6
1

Remove first block of tower one. Optimal result is 1.


Submit

Login to submit.

Statistics

70% Solution Ratio
curly_bracesEarliest, Dec '19
alamkhanFastest, 0.0s
obaydullahmhsLightest, 1.5 MB
jaberndcShortest, 629B
Toph uses cookies. By continuing you agree to our Cookie Policy.