<PREV Problem:
NEXT>
Solved by 42 users: vi002, dan, Mishunin_Alexander, vanger, JohnJones_001, rvashegin, ilyich, Rizvanov, tourist, sridhar87, pmnox, WsemirZ, mage, Glukenstein, wojtekt, zloy_mipt, Chmeli_BSU, Ravent, Philip_PV, lutyj, mazahaka, UdH-WiNGeR, defrager, RAVEman, Kuznetsov_S, topspin, piter, li0n, fetetriste, lm, EAA2008, Dest, ripatti, DAV, regmar, s01A15, tttttt, LiuChenheng, mmagnet, NIGHTFIT, mathematic, Robert_Gerbicz.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Time Management

Time limit = 2 second(s)

You've become a high quality IT specialist and you are earning a lot. You are receiving job offers from a lot of serious companies. You can participate in many big projects. You've also got some interesting ideas: to practice yoga, to visit Australia, Goa, Cuba, Iceland and Algeria, to sale your yacht in Mediterranean Sea. You also need to pass driver exam, study Japanese, graduate your Institue and so on.

Right now you've completely understand that you need exact Time Management. It's very good that this understanding came now and not after 20 or 50 years.

First, you need to effectively set your time on each task, to analyze that data and to come up with the most efficient schedule.

So you've put down all your planes for the next 50 years, divided them into small separate tasks (those tasks which take less that 20 minutes are not on scedule) and for each of them you've also set a time frame. This frame could be shifted forward or backward, but no more than 10 minutes.

You are ready to advance to next task as soon as you finish previous one (don't worry there also tasks like sleeping, eating, watching a movie).

Unfortunately, some task are overlapping.

But don't get upset! You are to write a program (you've decided to spend 30 minutes on that starting now), which can choose maximum number of non-overlapping tasks. After that you only need to follow that plan.

Input

First line contains number of tasks N, 1 < N < 50001. Each of next N lines contains two integer numbers from [0, 2000000000] --- beginning and ending of time frame (those are represented in minutes from some fixed moment in time).

Output

First line should contain integer nubmer K — maximum number of non-overlapping tasks. Next K lines should contain description of K chosen tasks. In each line: identifier of a task and shift of that task (integer nubmer from [-10,10]).

Input#1
4
30 66
1 30
6 38
20 52
Output#1
2
1 -10
3 0
Input#2
7
67 98
30 66
1 30
37 58
6 38
40 62
48 70
Output#2
4
2 -10
3 -10
6 0
0 3
Input#3
7
56 98
30 66
1 30
37 58
6 38
40 62
48 70
Output#3
3
2 -10
3 -10
6 0


Author:
Artem Voroztsov, Personal MIPT student programming contest, 7 October 2007. Translated by Mishik.
4 December 2007

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.198.246.116