JCHARD - Jamcode 2006 (Hard)

no tags 

There is one unnamed popular programming contest for people from all around the world. (Its name matches "SearchEngine Program Marmalade".) The contest starts with a coding phase where the contestants write code. After the coding phase there is a challenge phase. In this phase one can gain points when she finds a bug in someone else's code.

We were all lame and performed very badly. In fact, none of our programs worked. Thus we decided to hold a new contest: the Jam Code. Here, the task is to write a program that will never work correctly.

This contest will have an anti-challenge phase, where your goal is to find at least one test case such that a given program actually works ; in other words, it computes the correct answer.

Problem specification

You will be given a programming task and someone's source code. Find a valid input such that the program computes the correct answer.

Hard Task specification

You are organizing a big party for a lot of people. You want to invite 2N men and 2N women. At the beginning of the party, there will be a dance. Before the party, each man sent you a list of women he is willing to dance with. You have to maximize the number of pairs that can dance at the same time.

The first line of the input file contains an integer N (0< N and N < 100). On each of the next 2N lines there are 2N numbers. If the i-th number on the j-th line is 0, then the j-th man doesn't want to dance with the i-th woman. If the number is 1, the man is willing to dance with the woman.

Output one number on one line with the maximum number of pairs which can dance at the same time.

Example

Input
1
1 1
1 1

Output
2

The file jchard.cpp contains the program you are supposed to anti-challenge.

You are to submit a file which contains a valid input.



Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:TEXT
Resource:IPSC 2006