1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <map> 6 #define MP make_pair 7 using namespace std; 8 9 typedef pair<int, int> PII; 10 11 const int maxn = 1000 + 10; 12 const int INF = 0x3f3f3f3f; 13 14 PII a[maxn]; 15 int sum[maxn]; 16 17 int n, v, x; 18 19 int d[maxn][maxn][2]; 20 21 int main() 22 { 23 while(scanf("%d%d%d", &n, &v, &x) == 3) 24 { 25 for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second); 26 a[++n] = MP(x, 0); 27 sort(a + 1, a + 1 + n); 28 for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].second; 29 30 int p; 31 for(int i = 1; i <= n; i++) if(a[i].first == x) { p = i; break; } 32 memset(d, 0x3f, sizeof(d)); 33 d[p][p][0] = d[p][p][1] = 0; 34 35 for(int i = p; i > 0; i--) 36 for(int j = p; j <= n; j++) 37 { 38 if(i == j) continue; 39 int t = sum[i - 1] + sum[n] - sum[j]; 40 41 int& ans1 = d[i][j][0]; 42 ans1 = min(ans1, d[i+1][j][0] + (t + a[i].second) * (a[i+1].first - a[i].first)); 43 ans1 = min(ans1, d[i+1][j][1] + (t + a[i].second) * (a[j].first - a[i].first)); 44 45 int& ans2 = d[i][j][1]; 46 ans2 = min(ans2, d[i][j-1][0] + (t + a[j].second) * (a[j].first - a[i].first)); 47 ans2 = min(ans2, d[i][j-1][1] + (t + a[j].second) * (a[j].first - a[j-1].first)); 48 } 49 50 printf("%d ", min(d[1][n][0], d[1][n][1]) * v); 51 } 52 53 return 0; 54 }