Problem 25214 --分糖果

25214: 分糖果

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 88  Solved: 33
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

       whitecloth 有N 个糖果,小猫rainbow 和freda 来找whitecloth 要糖吃……对于每个糖果,rainbow 和freda 各有一个喜欢度ri 和fi,whitecloth不能不给他们糖果(他们会闹的),但又不想全给,于是whitecloth决定给他们恰好M 块糖果。为了让两只小猫不要闹矛盾,whitecloth 希望所给糖果的ri 的和与fi的和的差值的绝对值尽量小,在此基础上,whitecloth 还希望所有ri和fi 的总和最大,于是他请你来帮他出主意。

Input

第一行两个数N,M
接下来N 行,每行两个数ri,fi

Output

第一行一个数,表示最小的差值的绝对值
第二行一个数,表示最大的ri 和fi 的总和。

Sample Input

4 2
1 2
2 3
4 1
6 2

Sample Output

2
10

HINT

对于30%的数据,N<=20,M<=10


对于100%的数据,N<=200,M<=20,1<=ri,fi<=20,M<=N







注意数组下标为负如何处理

Source

[Submit][Status]