[Baltic2009]candy

时间限制:20s      空间限制:64MB

题目描述

给定N个数对(Si,Ti) ,表示时刻 Si时在位置 Ti处出现一粒糖果。有一些机器人可供使用,每个机器人可花费一单位时间向相邻位置移动。要求用最少的机器人接到全部糖果,并给出方案。时刻0时机器人位置可自行安排。


输入格式


输出格式


样例输入

9
32075317 158581561
170296294 29641357
225431181 2735545
290619056 114120555
83808165 304178313
105658380 52053836
35334005 20685922
204810947 300648081
84193939 85587943

样例输出

4
35334005 20685922 1
105658380 52053836 2
84193939 85587943 1
32075317 158581561 1
170296294 29641357 3
225431181 2735545 4
83808165 304178313 1
290619056 114120555 4
204810947 300648081 2

提示

1 ≤ n ≤ 100000 0 ≤ si,ti ≤ 1000000000 .................................. 这个题方案唯一?


题目来源

没有写明来源

Menuappsclose