배치 스케줄링

한 대의 기계에서 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 작업을 순서대로 처리한다. 작업 순서 $1, 2, \dots, N$을 하나 이상의 배치(batch) 로 나눈다. 각 배치는 순서상 연속한 작업들의 묶음이다.

처리는 시간 $0$에 시작한다. 배치는 첫 번째 배치부터 차례로 하나씩 처리하며, 더 작은 번호의 작업을 포함한 배치를 먼저 처리한다. 각 배치를 시작하기 전에는 기계를 준비하는 데 준비 시간 $S$가 필요하다.

어떤 배치가 작업 $x, x+1, \dots, x+k$로 이루어져 있고 시간 $t$에 시작한다면, 이 배치에 속한 모든 작업의 출력(완료) 시각은 $t + S + (T_x + T_{x+1} + \dots + T_{x+k})$ 이다. 기계는 한 배치의 모든 결과를 이 시각에 동시에 출력하며, 바로 이어서 다음 배치가 시작된다.

각 작업 $i$에는 처리 시간 $T_i$와 비용 계수 $F_i$가 주어진다. 작업 $i$의 출력 시각을 $O_i$라 하면 그 작업의 비용은 $O_i \times F_i$이다. 한 분할의 전체 비용은 모든 작업 비용의 합이다.

준비 시간과 각 작업의 처리 시간 및 비용 계수가 주어질 때, 가능한 전체 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 작업의 수 $N$이 주어진다 ($1 \le N \le 10000$).

둘째 줄에 준비 시간 $S$가 정수로 주어진다 ($0 \le S \le 50$).

이어지는 $N$개의 줄에는 작업 $1, 2, \dots, N$의 정보가 순서대로 주어진다. 각 줄에는 두 정수 $T_i$와 $F_i$가 주어지며, $T_i$는 그 작업의 처리 시간 ($1 \le T_i \le 100$), $F_i$는 비용 계수 ($1 \le F_i \le 100$)이다.

가능한 전체 비용의 최솟값을 한 줄에 하나의 정수로 출력한다.

모든 테스트 케이스에서, 어떤 분할이든 그 전체 비용은 $2^{31} - 1$을 넘지 않는다.