1177: 吃草(0π0)

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

New Orleans家的后院有很多片草坪,Sullivan负责清理过高的草。但是,Sullivan还有很多家务要干,于是,她想到了一个好方法。
后院总共有n片草坪,第i片草坪投影到数轴上,是一段l[i]到r[i]的闭区间,保证l[i]+r[i]是偶数,l[i]<=r[i]。
Sullivan可以在整点上放0v0来把草吃掉(于是0v0变成了0π0)。如果第i片草坪覆盖了x点上的0π0(l[i]<=x& lt;=r[i]),那么这只0π0就可以吃掉这片草坪里的草。每一片草坪的草需要且只能被一只0π0吃掉。如果一片草坪覆盖了多只 0π0,Sullivan可以选择任意一只去吃草。
但是,0π0吃草是有代价的,对于第i片草坪,假如吃草的0π0位于x点上,代价为abs((x-l[i])-(r[i]-x)),即0π0到草坪两端距离之差。
现在,Sullivan想知道:
1.最少需要放几只0v0?
2.在放最少只数的0v0情况下,代价最小是多少?

Input

第一行两个正整数n,t。
第二行到第n+1行,第i+1行两个正整数l[i],r[i]。

Output

第一行一个非负整数,为最小的0v0数量。
如果t=0,没有第二行输出;如果t=1,第二行输出在放最少只数的0v0情况的最小代价。

Sample Input Copy

3 1
1 11
2 4
5 7

Sample Output Copy

2
0

HINT

20% n,l[i],r[i]<=3000 t=0
30% n,l[i],r[i]<=300000 t=0
20% n,l[i],r[i]<=3000 t=1
30% n,l[i],r[i]<=300000 t=1


样例解释

在3上与6上各放一只0v0即可