1240: 零件加工

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

Description

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

Input

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

Output

输出仅一行，一个整数，表示小K最少要缴纳的罚金对m取模的结果。

Sample Input Copy 

2
100 
2 33 
33 2

Sample Output Copy 

4