问题描述

为了乘坐飞艇离开天空之城，Elizabeth 要去工厂寻找修复飞艇的工具。由于物资紧缺，他们必须帮工厂完成一定的任务才能获得零件，并且生产成本自负。Elizabeth 的自由之路才踏出第一步，所以他们要尽可能省钱，以备不时之需。

有一个机器，它有 $N$ 个任务需要按顺序完成，它们可以被分为若干组按顺序完成，开始时刻为 $0$。第 $i$ 个任务单独完成的时间为 $T_i$。 完成一组任务之前机器需要 $S$ 的时间启动，完成这组任务所用的时间为这组任务所有 $T_i$ 的和。同一组任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以它的费用系数 $F_i$。

请你来帮她确定最小总费用供她参考。

输入格式

第一行两个正整数 $N,S$。接下来 $N$ 行，每行两个整数 $T_i,F_i$。

输出格式

一行一个整数表示最小总费用。

样例

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

153

按顺序完成 $(1,2)$，$(3)$，$(4,5)$ 括号表示分组：

• 第一组完成时刻为 $1+1+3=5$，$ans+5*(2+3)$
• 第二组完成时刻为 $5+1+4 =10$，$ans+10*3$
• 第三组完成时刻为 $10+1+2+1=14$，$ans+14*(3+4)$

数据范围

• 对于 $100\%$ 的数据：$n\le 3000$，$0\le S,T_i,F_i\le 512$