### 题目描述

#### 输出格式

##### 输入输出样例

5 3
2 10
3 20
5 20
6 30
8 10

###### 输出 #1

270

{此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序}

$f\left[i\right]\left[j\right]\left[0\right]=min\left(f\left[i+1\right]\left[j\right]\left[0\right]+\left(w\left[i+1\right]-w\left[i\right]\right)\ast c,f\left[i+1\right]\left[j\right]\left[1\right]+\left(w\left[j\right]-w\left[i\right]\right)\ast c\right);$
$f\left[i\right]\left[j\right]\left[1\right]=min\left(f\left[i\right]\left[j-1\right]\left[0\right]+\left(w\left[j\right]-w\left[i\right]\right)\ast c,f\left[i\right]\left[j-1\right]\left[1\right]+\left(w\left[j\right]-w\left[j-1\right]\right)\ast c\right);$
$c$指的是还没关的灯每秒耗电量的总和，这个用前缀和一减就可以得到。

##### 下面是代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int f[55][55][2], s[55], w[55];
int main(){
memset(f, 1, sizeof(f));
int i, j, n, m, c;
scanf("%d%d", &n, &c);
for(i = 1; i <= n; i++){
scanf("%d%d", &w[i], &s[i]);
s[i] += s[i-1];
}
f[c][c][0] = f[c][c][1] = 0;
for(i = n; i >= 1; i--){
for(j = i + 1; j <= n; j++){
c = s[n] - (s[j] - s[i]);
f[i][j][0] = min(f[i+1][j][0] + (w[i+1] - w[i]) * c, f[i+1][j][1] + (w[j] - w[i]) * c);
c = s[n] - (s[j-1] - s[i-1]);
f[i][j][1] = min(f[i][j-1][0] + (w[j] - w[i]) * c, f[i][j-1][1] + (w[j] - w[j-1]) * c);
}
}
printf("%d", min(f[1][n][0], f[1][n][1]));
return 0;
}