单机调度问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


对于给定的n个互不相同的子任务 J1 , J2 , ……, J ,和这n个子任务需要时间和空间,以及系统调整时间x,计算全部完成n个子任务的最小费用。

Input

输入数据的第一行有2 个整数n和x,表示有n个互不相同的子任务,新时间段开始工作之前需要系统调整时间x。接下来的n 行中每行有2 个整数t 和s,表示相应的子任务需要时间t 和空间s。n≤200000,0≤x≤5。

Output

将计算出的最小费用输出。在所有测试数据中,均假定从时间0开始。

Sample Input

5 1
1 3
3 2
4 3
2 3
1 4

Sample Output

153

Hint

 

Source