National Olympiad in Informatics, China, 2011

NOI 2011 at Jilin University has started! To welcome outstanding informatics competitors from across the country, Jilin University has decided to host two magnificent NOI carnivals at two different venues. Each venue contains many different events, and each event can only be held in one of the venues.

Little Andy, the carnival event organizer, has received a total of $n$ event applications. The $i$-th event starts at $S_i$ and has a duration of $T_i$. Each event may be scheduled at any one venue, or not scheduled at all.

After extensive surveying, Andy discovered that at any given time, if both venues are simultaneously hosting events (excluding the instant when events start or end), competitors will be distraught over deciding between which venue to attend. To prevent this unpleasant scenario, Andy requires that no two events may be simultaneously held at both venues. Multiple events at the same venue may be held as pleased.

As one may imagine, if a certain venue contains too few events, then its appeal will not be so great, leading to a deserted site. Andy wishes to make an appropriate schedule such that the number of events at the venue with the fewest events is as large as possible.

Additionally, some events are very interesting and Andy would like to try to host them. He wishes to know, if the $i$-th event must be held (it may be held at either one of the venues), what is the maximum number of events that can be held at the venue with the fewest events.

Input Specification

The first line contains an integer $n$, representing the number of events.
For the following $n$ lines, each line describes a single event. The $i$-th of these lines contains two integers $S_i$ and $T_i$, indicating that event $i$ will start at $S_i$ and last $T_i$ units of time.

Output Specification

The first line of output should contain a single integer, representing the maximum number of events that can be held at the venue with the fewest events, without any extra restrictions about which event must be held.
The following $n$ lines should each contain a single integer. The $i$-th of these lines should contain the maximum number of events that can be held at the venue with the fewest events, under the precondition that event $i$ must be held.

Sample Input

5
8 2
1 5
5 3
3 2
5 3

Sample Output

2
2
1
2
2
2

Explanation

When there are no extra constraints, events $1$ and $4$ should be scheduled at one venue, and events $3$ and $5$ should be scheduled at the other venue. Event $2$ is not scheduled.

Scoring

For each test case, your score out of $10$ is determined as follows:

• If the output format is invalid (e.g. there are fewer than $n+1$ lines), then your score will be $0$.
• If the first line is incorrect, and at least one of the following $n$ lines is incorrect, then your score will be $0$.
• If the first line is correct, but at least one of the following $n$ lines is incorrect, then your score will be $4$.
• If the first line is incorrect, but all of the following $n$ lines are correct, then your score will be $6$.
• If all $n+1$ lines in the output are correct, then your score will be $10$.

Constraints

The attributes of all the test cases are outlined below.

Test Case	Range of $n$	Constraints
$1$	$1\le n\le 10$	$0\le S_i\le {10}^9$ $1\le T_i\le {10}^9$
$2$	$1\le n\le 40$
$3$
$4$	$1\le n\le 200$
$5$
$6$
$7$
$8$
$9$
$10$

Problem translated to English by Alex.