Knights
(Running time - 1s.)
We are given a chess-board of size n*n, from which some fields
have been removed. The task is to determine the maximum number of knights
that can be placed on the remaining fields of the board in such a way that
none of them check each other.
Fig.1: A knight placed on the field S checks fields marked with x.
Task
Write a program, that:
-
reads the description of a chess-board with some fields removed, from the
input file kni.in,
-
determines the maximum number of knights that can be placed on the chess-board
in such a way that none of them check each other,
-
writes the result to the output file kni.out.
Input
The first line of the input file kni.in contains two integers
n and m, separated by a single space, 1<=n<=200,
0<=m<n2; n is the chess-board size and m
is the number of removed fields. Each of the following m lines contains
two integers: x and y, separated by a single space, 1<=x,y<=n
-- these are the coordinates of the removed fields. The coordinates of
the upper left corner of the board are (1,1), and of the bottom right are
(n,n). The removed fields are not repeated in the file.
Output
The output file kni.out should contain one integer (in the first
and only line of the file). It should be the maximum number of knights
that can be placed on the given chess-board without checking each other.
Example
Input file kni.in:
3 2
1 1
3 3
correct output file kni.out
5