There are $NN$ tasks arranged in a sequence on a machine waiting to be executed, and their order cannot be changed. You need to divide these $NN$ tasks into several groups, each containing several consecutive tasks. Starting from time 0, the tasks are processed in groups, and the time required to execute the $ii$-th task is $T_{i}T\_i$. Additionally, the machine requires a startup time $SS$ before each group of tasks begins, so the time required for a group of tasks is the startup time $SS$ plus the sum of the time required for each task in this group.

After a task is executed, it will wait briefly in the machine until all tasks in that group are completely executed. That is to say, the tasks in the same group will be completed at the same time. The cost of each task is its completion time multiplied by a cost coefficient $C_{i}C\_i$.

Please plan a grouping scheme for the machine to minimize the total cost.

For all testing data, $1\le N\le 1000,0\le S\le 50,1\le T_i,C_i\le 1001\backslash le\; N\; \backslash le\; 1000,\; 0\; \backslash le\; S\; \backslash le\; 50,\; 1\backslash le\; T\_i,\; C\_i\; \backslash le\; 100$

Function Interface:

long long min_cost(int N, int S, int T[], int C[]);

where T, C are arrays of integers with N elements, and S is the startup time $SS$ mentioned above.

Judge Program:

#include <stdio.h>
#define MAXN 1000
long long min_cost(int N, int S, int T[], int C[]);
int main() {
    int N, S;
    int T[MAXN], C[MAXN];
    scanf("%d%d", &N, &S);
    for (int i = 0;i < N; ++ i) {
        scanf("%d%d", &T[i], &C[i]);
    }
    printf("%lld\n", min_cost(N, S, T, C));
    return 0;
}
/* Your function will be put here */

Sample Input:

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

Sample Output：

153

Sample Explanation

We have grouped the tasks into 3 groups, which are {1, 2}, {3}, {4, 5}. The completion time corresponding to each task, in the order of the task numbers, is {5, 5, 10, 14, 14}. Similarly, the cost corresponding to each task, again in the order of the task numbers, is {15, 10, 30, 42, 56}. The total cost of these tasks is 153.