Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Jenga Tower

By TarikHassan · 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.



Discussion
Statistics

70% Solution Ratio

curly_bracesEarliest, 1M ago

alamkhanFastest, 0.0s

obaydullahmhsLightest, 1.5 MB

jaberndcShortest, 629B

Submit

Login to submit