Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,K=[int(val) for val in input().split()]

list_x=list()
list_y=list()
list_z=list()

ans=float('inf')

for i in range(N):
  x,y=(int(val) for val in input().split())
  list_x.append(x)
  list_y.append(y)
  list_z.append((x,y))

list_x.sort()
list_y.sort()

for i in list_y:
  for j in list_y:
    for k in list_x:
      for l in list_x:
        cnt=0
        for m in range(len(list_z)):
          if l<=list_z[m][0]<=k and j<=list_z[m][1]<=i:
            cnt+=1
          if K <= cnt:
            tmp=(i-j)*(k-l)
            if tmp < ans:
              ans=tmp

print(ans)




### FIXED CODE ###

import sys
input = sys.stdin.readline

N,K=[int(val) for val in input().split()]

list_x=list()
list_y=list()
list_z=list()

ans=float('inf')

for i in range(N):
  x,y=(int(val) for val in input().split())
  list_x.append(x)
  list_y.append(y)
  list_z.append((x,y))
#  heapq.heappush(list_x, x)
#  heapq.heappush(list_y, y)
list_x.sort()
list_y.sort()

for i in list_y:
  for j in list_y:
    if i<=j:
      break
    else:
      for k in list_x:
        for l in list_x:
          if k<=l:
            break
          else:
            cnt=0
            for m in range(len(list_z)):
              if l<=list_z[m][0]<=k and j<=list_z[m][1]<=i:
                cnt+=1
              if K <= cnt:
                tmp=(i-j)*(k-l)
                if tmp < ans:
                  ans=tmp
                break

print(ans)
### BUGGY CODE ###

import numpy as np

N = list(map(int,input().strip().split()))
alist = list(map(int,input().strip().split()))
ans = float("inf")

s = np.array([i for i in range(len(alist))])
slist = alist-s

for i in range(len(alist)):
    num = 0
    xlist = list(map(lambda x:abs(x-slist[i]), slist))
    num = sum(xlist)
    if ans > num:
        ans = num

print(ans)

### FIXED CODE ###

import numpy as np

N = int,input()
alist = list(map(int,input().strip().split()))

s = np.array([i for i in range(len(alist))])
slist = alist-s
slist.sort()

abs_slist = list(map(lambda x:abs(x-slist[len(slist)//2]), slist))

print(sum(abs_slist))
### BUGGY CODE ###

n = int(input())
c = str(input())
cn = [False]*n
for i in range(n):
    if c[i]=="R":
        cn[i]= True


ans = 0
k=n-1
b=0

for i in range(n):
    if b==1:
        break

    if cn[i]== 0:
        for j in range(k,0,-1):

            if cn[j]==1:
                k =j
                if i < j:
                    cn[i]=1
                    cn[j]=0
                    ans +=1
                    break
                elif i>=j:
                    b=1
                    break
print(ans)

### FIXED CODE ###

n = int(input())
c = str(input())
cn = [False]*n
for i in range(n):
    if c[i]=="R":
        cn[i]= True


ans = 0
k=n-1
b=0

for i in range(n):
    if b==1:
        break

    if not(cn[i]):
        for j in range(k,0,-1):

            if cn[j]:
                k =j-1
                if i < j:
                    #cn[i]=True
                    #cn[j]=False
                    ans +=1
                    break
            if i>=j:
                b=1
                break
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())

wv = (map(int, input().split()) for _ in range(N))

dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        dp[j] = max(dp[j], DP)

print(max(dp))


### FIXED CODE ###

def dp():
    n, W = map(int, input().split())
    wv = (map(int, input().split()) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in wv:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(dp())
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
l = list( map(int, input().split())) 
ans = 0
l.sort()

for i in range(n-2):
    shortest = l[i]
    for j in range(i+1, n-1):
        second = l[j]
        k = bisect_left(l[j+1:], shortest + second)
        ans += k

print(ans)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list( map(int, input().split())) 
ans = 0
l.sort()

for i in range(n-2):
    shortest = l[i]
    for j in range(i+1, n-1):
        second = l[j]
        # このスライスしたやつと地味にTLEになる...
        # k = bisect_left(l[j], shortest + second)
        # ans += k

        k = bisect_left(l, shortest + second)
        ans += k - j - 1

print(ans)
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
h = list(map(int,input().split()))
cost = [float('inf')]*N

cost[0] = 0
for i in range(N-1):
  l = min(i,K-1)
  for j in range(l+1):
    num2 = cost[i-j] + abs(h[i+1]-h[i-j])
    if cost[i+1] > num2:
      cost[i+1] =  num2
      
print(cost[N-1])

### FIXED CODE ###

N,K = (int(x) for x in input().split())
h = list(map(int,input().split()))
cost = [float('inf')]*N

cost[0] = 0
for i in range(N-1):
  l = min(i,K-1)
  for j in range(l+1):
    num2 = cost[i-j] + abs(h[i+1]-h[i-j])
    if cost[i+1] > num2:
      cost[i+1] =  num2
      
print(cost[N-1])
### BUGGY CODE ###

N = int(input())
X = int(input(), 2)

for i in range(N - 1, -1, -1) :
  x = X ^ (1 << i)
  
  ret = 0
  while x != 0 :
    x = x % bin(x).count('1')
    ret += 1

  print(ret)

### FIXED CODE ###

N = int(input())
X = int(input(), 2)

M = 2 * (10 ** 5) + 10
ret = [0] * (M + 1)
for i in range(M + 1) :
  x = i
  c = 0
  while x != 0 :
    x = x % bin(x).count('1')
    c += 1
  ret[i] = c
  
p = bin(X).count('1')
a = X % (p + 1)
if p > 1 :
  b = X % (p - 1)

for i in range(N - 1, -1, -1) :
  if (1 << i) & X :
    if p == 1 :
      print(0)
    else :
      print(ret[(b - pow(2, i, p - 1)) % (p - 1)] + 1)
  else :
    print(ret[(a + pow(2, i, p + 1)) % (p + 1)] + 1)
### BUGGY CODE ###

import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
S = inputs[1:]

for i in range(n):
    S[i] = ''.join(sorted(list(S[i])))
S.sort()

ans = 0
for i in range(n-1):
    query = S[i]
    for j in range(i+1, n):
        if query == S[j]:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict
inputs = sys.stdin.readlines()

n = int(inputs[0])
S = inputs[1:]

d = defaultdict(lambda: -1)
for i in range(n):
    s = ''.join(sorted(list(S[i].rstrip())))
    d[s] += 1

ans = 0
for v in d.values():
    ans += v*(v+1)//2
print(ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split(" "))
A = np.arange(1, N + 1)
for m in range(M):
    L, R = map(int, input().split(" "))
    A = A[L <= A]
    A = A[A <= R]
print(len(A))



### FIXED CODE ###

N, M = map(int, input().split(" "))
L = 1
R = N
ans = 0
for m in range(M):
    L_in, R_in = map(int, input().split(" "))
    if L_in > L:
        L = L_in
    if R_in < R:
        R = R_in
if L > R:
    ans = 0
else:
    ans = R - L + 1
print(ans)
### BUGGY CODE ###

import math 
import sys
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
A.sort()

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= MAX:
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1

print("pairwise coprime")



### FIXED CODE ###

import math 
import sys
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
A.sort()

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
lim = math.ceil(math.sqrt(MAX))
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= lim and b > 1:
    if p in visited: 
      p += 1
      continue
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1
  if b > 1:
    q = b
    p = b
    for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
      visited.add(q) 
      
      

print("pairwise coprime")



"""
def raise_prime(B):
  n = len(B)
  if n == 1:
    
  C = B[0: n//2]
  D = B[n//2:n]
"""


  
  
"""
for a in A:
  p = 2
  while p <= N:
    if p not in visited:
      
      
    
  
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    union.add()
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
"""
### BUGGY CODE ###

def expectation(li):
  total = 0
  for i in li:
    total += (i+1)/2
  return total

n,k = map(int,input().split())
p = list(map(int,input().split()))
M = 0
for i in range(n-k+1):
  li = p[i:i+k]
  total = expectation(li)
  if total > M:
    M = total
print(M)


### FIXED CODE ###

def expectation(li):
  total = 0
  for i in li:
    total += (i+1)/2
  return total

n,k = map(int,input().split())
p = list(map(int,input().split()))
ex = expectation(p[0:k])
li = [ex]
for i in range(1,n-k+1):
  ex = ex - (p[i-1]+1)/2 + (p[i+k-1]+1)/2
  li.append(ex)
print(max(li))
### BUGGY CODE ###

n, k = map(int, input().split(" "))
ps = list(map(int, input().split(" ")))

max = 0
for i in range(n-k+1):
  if i == 0:
    s = sum(ps[i:i+k])
  else:
    s = s - (ps[i-1] - ps[i+k-1])
  s = sum(ps[i:i+k])
  if s > max:
    max = s
print((max + k) / 2)

### FIXED CODE ###

n, k = map(int, input().split(" "))
ps = list(map(int, input().split(" ")))

max = 0
for i in range(n-k+1):
  if i == 0:
    s = sum(ps[i:i+k])
  else:
    s = s - (ps[i-1] - ps[i+k-1])
  if s > max:
    max = s
print((max + k) / 2)
### BUGGY CODE ###

def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    t = sum(max(0, (m - w) // d + 1) for w, d in flowers)
    if t < k:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, k = map(int, input().split())
flowers = [tuple(map(int, input().split())) for _ in range(n)]
print(solve(1, flowers[0][0] + flowers[0][1] * k))


### FIXED CODE ###

from bisect import bisect


def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    j = bisect(flowers, (m, float('inf')))
    t = sum((m - w) // d + 1 for w, d in flowers[:j])
    if t < k:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, k = map(int, input().split())
flowers = [tuple(map(int, input().split())) for _ in range(n)]
flowers.sort()
print(solve(1, flowers[0][0] + flowers[0][1] * k))
### BUGGY CODE ###

n = int(input())
s = list(input())
m = 3 * 10 ** 5
for i in range(n):
    count = 0
    for j in range(0, i):
        if s[j] == 'W':
            count += 1
    for k in range(i + 1, n):
        if s[k] == 'E':
            count += 1
    m = min(m, count)

print(m)

### FIXED CODE ###

N = int(input())
S = list(input())

reS = S[::-1]

wSum = [0 for i in range(N)]
eSum = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        if S[i] == 'W':
            wSum[i] = 1
        if reS[i] == 'E':
            eSum[i] = 1
    else:
        if S[i] == 'W':
            wSum[i] = wSum[i-1] + 1
        else:
            wSum[i] = wSum[i-1]
        if reS[i] == 'E':
            eSum[i] = eSum[i-1] + 1
        else:
            eSum[i] = eSum[i-1]

eSum = eSum[::-1]

cost = eSum[1]

for i in range(1,N):
    if i == N - 1:
        if cost > wSum[N-2]:
            cost = wSum[N-2]
    else:
        if cost > wSum[i-1] + eSum[i+1]:
            cost = wSum[i-1] + eSum[i+1]
print(cost)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
s=set(a)
ans=0
for i in s:
    j=a.count(i)
    if j<i:
        ans+=j
    if i<j:
        ans+=j-i
print(ans)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
a.sort()
C=[0]
s=[a[0]]
for i in a:
    if(s[-1]==i):
        C[-1]+=1
    else:
        C.append(1)
        s.append(i)
ans=0
for i in range(len(s)):
    if C[i]<s[i]:
        ans+=C[i]
    else:
        ans+=C[i]-s[i]
print(ans)
### BUGGY CODE ###

# BFS queue
import queue
import copy
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)


### FIXED CODE ###

# BFS queue
import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
l = 0
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
            l += 1
if l >= H*W-(H-2):
    print(H+W-2)
    exit()
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if ttt-sss >= 1:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)
### BUGGY CODE ###

def solve(n, k, h_list):
    inf = 10 ** 9
    dp = [inf] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k + 1):
            if i - j < 0:
                continue
            dp[i] = min(dp[i], dp[i - j] + abs(h_list[i] - h_list[i - j]))

    return dp[n - 1]


def main():
    n, k = map(int, input().split())
    h_list = list(map(int, input().split()))

    ans = solve(n, k, h_list)
    print(ans)


main()

### FIXED CODE ###

import numpy as np


def solve(n, k, h_list):
    dp = np.zeros(n, dtype=int)

    for end in range(1, n):
        start = max(0, end - k)
        dp[end] = np.min(dp[start:end] + np.abs(h_list[end] - h_list[start:end]))

    return dp[n - 1]


def main():
    n, k = map(int, input().split())
    h_list = np.array(input().split(), dtype=int)

    ans = solve(n, k, h_list)
    print(ans)


main()
### BUGGY CODE ###

def make_divisors(n):
    divisors = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors += 1
            if i != n // i:
              divisors += 1
    return divisors

num = int(input())
ans = 0
for i in range(1, num):
  ans += make_divisors(i)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
  ans += (N-1) // a

print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
mod = (10**9) + 7
t = 0
for i in range(n-1):
    for j in range(i+1,n):
        t += ((A[i]%mod) * (A[j]%mod))%mod
        t = t%mod
print(t)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
mod = (10**9) + 7
t = 0
sum = 0
for i in range(1,n):
    sum += A[i]
for i in range(n-1):
    t += (A[i]*sum)%mod
    sum -=  A[i+1]
t = t%mod
print(t)
### BUGGY CODE ###

N, M, Q = map(int, input().split())

import numpy as np
matrix = np.array([[0 for _ in range(N+1)] for _ in range(N+1)])

for L, R in (map(int, input().split()) for _ in range(M)):
    matrix[:L+1,R:] += 1

for p, q in (map(int, input().split()) for _ in range(Q)):
    print(matrix[p,q])


### FIXED CODE ###

N, M, Q = map(int, input().split())

class Cell:
    def __init__(self):
        self.value = 0
        self.L = 0
    def __repr__(self):
        return str((self.value, self.L))

pairs = [[Cell() for _ in range(N+1)] for _ in range(N+1)]
for L, R in (map(int, input().split()) for _ in range(M)):
    cell = pairs[L][R]
    cell.value += 1
    cell.L = cell.value

for i in range(N-1, 0, -1):
    for j in range(i+1, N+1):
        cell = pairs[i][j]
        cell.L += pairs[i][j-1].L
        cell.value = cell.L + pairs[i+1][j].value
for p, q in (map(int, input().split()) for _ in range(Q)):
    print(pairs[p][q].value)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = []
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*5005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,5000),0))
    fin=[False]*n
    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        fin[u]=True
        if sum(fin)==n:break
        c,d=cd[u]
        for i in range(1,10000):
            if g+c*i>5000:
                if dp[u][5000] <= t + d * i: continue
                dp[u][5000] = t + d * i
                heappush(hp, (t + d * i, 5000, u))
                break
            if dp[u][g+c*i]<=t+d*i:continue
            dp[u][g + c * i]=t+d*i
            heappush(hp,(t+d*i,g+c*i,u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()

### FIXED CODE ###

from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*3005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,3000),0))
    dp[0][min(s,3000)]=0

    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        c,d=cd[u]
        if g+c<3000:
            if dp[u][g + c] > t + d:
                dp[u][g + c] = t + d
                heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][3000] > t + d:
                dp[u][3000] = t + d
                heappush(hp, (t + d, 3000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()
### BUGGY CODE ###

from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))

@lru_cache(None)
def dfs(d,pre):
    if d>=N-1: return 0
    ans = 0
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            ans = max(res,ans)
    return ans

print(dfs(-1,-1))


### FIXED CODE ###

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))

dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j]= A[i][j]
        else:
            tmp = [0] 
            for k in range(3):
                if j !=k:
                    tmp.append(dp[i-1][k])
            dp[i][j] = max(tmp) + A[i][j]
print(max(dp[-1]))
### BUGGY CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))
L=[]
R=[]
ans=0
for i in range(n):
    L.append(i-a[i])
    R.append(i+a[i])
    ans+=L.count(R[i])+R.count(L[i])

print(ans)

### FIXED CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))
L={}
R={}
ans=0
for i in range(n):
    L.setdefault(i-a[i],0)
    R.setdefault(i+a[i],0)
    L[i-a[i]]+=1
    R[i+a[i]]+=1
    
    if (i-a[i] in R):
        ans+=R[i-a[i]]
        #print(ans,L[i-a[i]])
    if (i+a[i] in L):
        ans+=L[i+a[i]]

print(ans)
#print(L)
#print(R)