#include using namespace std; #define ll long long #define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++) int n; vector pos, cnt; vector > dp, ndp; const ll INF = 1e18; ll dist(int i, int j) { return abs(pos[i] - pos[j]); } ll pref(int i, int j) { return cnt[j + 1] - cnt[i]; } int main(void) { ios_base::sync_with_stdio(false); ll start; cin >> n >> start; pos.resize(n), cnt.resize(n + 1); // v cnt budou uloženy prefixové součty, proto + 1 rep(i, 0, n) cin >> pos[i] >> cnt[i + 1]; rep(i, 0, n) cnt[i + 1] += cnt[i]; // dp uržuje aktuální řádek DPčka. V i-tém kroku je v dp[j] uložena // nejnižší cena, jak Karkulka může obsloužit všechny domy [j … j + i]. // (.first/.second = Karkulka skončí nalevo/napravo) dp.resize(n); ndp.resize(n); ll sum = pref(0, n - 1); // kolik celkem letáků rep(i, 0, n) dp[i].first = dp[i].second = sum * abs(start - pos[i]); rep(i, 0, n - 1) { rep(i, 0, n) ndp[i] = {INF, INF}; rep(l, 0, n - i) { int r = l + i; ll rem = sum - pref(l, r); // zprasené, ale úsporné #define IMPROVE(a, b, c, d, ee) ndp[a].b = min(ndp[a].b, dp[c].d + ee); if (l) { IMPROVE(l - 1, first, l, first, rem * dist(l, l - 1)); IMPROVE(l - 1, first, l, second, rem * dist(r, l - 1)); } if (r != n - 1) { IMPROVE(l, second, l, first, rem * dist(l, r + 1)); IMPROVE(l, second, l, second, rem * dist(r, r + 1)); } } dp = ndp; } cout << min(dp[0].first, dp[0].second) << endl; }