Odd or Even

Interview

Time limit3sMemory limit128 MB

Summary
Pair each red number with a blue number to minimize how many pairs sum to an even value, since Mary wins those.
Level

Medium5 of 10

Topics
Greedy, Math, Combinatorics, Implementation
Solved
No attempts yet

Problem

Odd or Even is a game two players use to settle random questions (for example, "who has to solve this problem?"). In one version, before playing each player calls out either odds or evens. The players then count to three, and on three both simultaneously hold out one hand showing from zero to five fingers. If the total number of fingers is even, the player who called evens wins; if the total is odd, the player who called odds wins.

John and Mary played several games of Odd or Even. In every game John called odds, so Mary always had evens. After each game both players recorded, on a small card, how many fingers they had shown — Mary wrote on blue cards and John on red cards — so they could review the results later. At the end of the day John dropped the whole deck. They could still sort the cards by color, but within each color the cards are now shuffled and the original game-by-game pairing is lost.

Given the multiset of numbers on the red cards and the multiset of numbers on the blue cards, write a program that determines the minimum number of games Mary is guaranteed to have won.

Input

The input contains several test cases. The first line of each test case has an integer NN, the number of games played (1≤N≤1001 \le N \le 100). The second line has NN integers XiX_i, the number of fingers Mary showed in each game (0≤Xi≤50 \le X_i \le 5). The third line has NN integers YiY_i, the number of fingers John showed in each game (0≤Yi≤50 \le Y_i \le 5). A line containing a single 00 marks the end of the input and must not be processed.

Output

For each test case, print a single line with one integer: the minimum number of games Mary is guaranteed to have won.

Examples3

  1. Example 1

    Input
    3
    1 0 4
    3 1 2
    9
    0 2 2 4 2 1 2 0 4
    1 2 3 4 5 0 1 2 3
    0
    
    Expected output
    0
    3
    
  2. Example 2

    Input
    1
    0
    0
    0
    
    Expected output
    1
    
  3. Example 3

    Input
    1
    1
    0
    0
    
    Expected output
    0