问题 26002 --零件加工

26002: 零件加工

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 20
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][17344kb]

题目描述

      工匠小K最近有n个零件需要加工。每个零件都需要ti天的时间来完成,每个零件每延迟一天加工都要缴纳一定的罚金si。延迟的天数为从今天算起到该工作开始的那天,第一个零件加工没有罚金。现在小K想知道怎样安排加工顺序可以使他要交的罚金最少,最少是多少。
      这个数可能会很大,请输出这个数对m取模后的结果。

输入

输入文件名为process.in。
输入第一行为一个整数n,表示需要加工的零件总数。
第二行为一个整数m,表示答案要对m取模。
第3~n+2行,每行两个整数ti和si。

输出

输出文件名为process.out。
输出仅一行,一个整数,表示小K最少要缴纳的罚金对m取模的结果。

样例输入

2
100 
2 33 
33 2

样例输出

4

提示


【输入输出样例解释1】



 



先加工第一个,需要2天时间,再加工第二个。需要缴纳的罚金为2×2=4。



 



【输入输出样例2】process.in                       



4



100



3 3



6 4



2 2



8 5                                



 



process.out



81



 



【输入输出样例解释2】



如果按照1→2→3→4的顺序进行加工,需要缴纳的罚金为0×3+3×4+(3+6)×2+



(3+6+2)×5=85;



最佳方案是3→1→2→4,此时需要缴纳的罚金为0×2+2×3+(2+3)×4+(2+3+6)×5=81。



【数据范围】



对于40%的数据,0<n≤10,000,0<ti,si≤10,000;



对于80%的数据,0<n≤100,000,0<ti,si≤2×109,0<m≤108


对于100%的数据,0<n≤100,000,0<ti,si≤2×109,0<m≤1018

来源

[提交][状态]