#!/usr/bin/python3 def intline(): """Přečte řádek čísel a vrátí je v seznamu""" return list(map(int, input().split())) def mkpref(v): """Vrátí funkci, které se můžeme ptát na intervalové součty nad polem v.""" pref = [0] for a in v: pref.append(pref[-1] + a) def answer(a, b): """Kolik je v[a] + … + v[b]?""" return pref[b + 1] - pref[a] return answer def mkdist(pos): """Vrátí funkci, která dostane indexy dvou domů a vrací jejich vzdálenost.""" def dist(a, b): return abs(pos[a] - pos[b]) return dist # Verze s anonymní funkcí: # return lambda a, b: abs(pos[a] - pos[b]) n, start = intline() pos, count = zip(*(intline(2) for i in range(n))) # f(*[a, b, c, ...]) = f(a, b, c, ...) # zip((a1, b1), (a2, b2), …) = (a1, a2, …), (b1, …) pos, count = list(pos), list(count) # zip vrací generátor, my chceme seznamy (abychom je mohli procházet vícekrát) INF = float("infinity") pref = mkpref(count) total = pref(0, n - 1) # Celkový počet letáků, které chceme roznést dist = mkdist(pos) # pro připomenutí, pref i dist jsou funkce # dp nám udržuje aktuální řádek DPčka. V i-tém kole je na dp[j][b] uložena # nejmenší možná námaha, jak roznést letáky, aby byla vyřízená oblast [j … j + # i] a Karkulka skončila ["nalevo", "napravo"][b]. dp = [total * abs(start - pos[i]), total * abs(start - pos[i]) for i in range(n)] for i in range(0, n -1): # i označuje aktuální šířky stavů, které počítáme. ndp = [(INF, INF)] * n # ndp počítá nový řádek DP. for j in range(0, n - i): l, r = j, j + i remains = total - pref(l, r) # kolik musíme roznést if l: a, b = ndp[l - 1] a = min(a, dp[l][0] + remains * dist(l, l - 1)) a = min(a, dp[l][1] + remains * dist(r, l - 1)) ndp[l - 1] = a, b if r < n - 1: a, b = ndp[l] b = min(b, dp[l][0] + remains * dist(r + 1, l)) b = min(b, dp[l][1] + remains * dist(r+1, r)) ndp[l] = a, b dp = ndp res = min(dp[0][0], dp[0][1]) print(res)