시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

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 Si and has a duration of Ti. Each events 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 an 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 than can be held at the venue with the fewest events.

입력

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 will contain two integers Si and Ti, indicating that event iwill start at Si and last Ti units of time.

출력

The first line of output should contain a single integer, representing the maximum number of events than 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 than can be held at the venue with the fewest events, under the precondition that event i must be held.

제한

  • 1 ≤ ≤ 200
  • 0 ≤ Si ≤ 109
  • 1 ≤ Ti ≤ 109

예제 입력 1

5
8 2
1 5
5 3
3 2
5 3

예제 출력 1

2
2
1
2
2
2