import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 101
#m = 4
dp = [[-1]*m for _ in range(n)]


from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))

while len(h) > 0:
    t,g,i = h[0]
    g = -g
#    print("t,g,i", t,g,i)
    # 
    heappop(h)

    if dp[i][min(g,m-1)] != -1:
        dp[i][min(g,m-1)] = min(t, dp[i][min(g,m-1)])
    else:
        dp[i][min(g,m-1)] = t
    
    for v,a,b in edges[i]:
        if g-a >= 0 and dp[v][min(g-a,m-1)] == -1:
            heappush(h,(t+b,-(g-a),v))
#            print("push", t+b,-g+a,v)

    c,d = cd[i]
    if dp[i][min(g+c,m-1)] == -1:
        heappush(h,(t+d,-(g+c),i))

for d in dp:
    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)
        


### FIXED CODE ###

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

MOD = 2019

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res    
s=s_in()

from collections import Counter


p = 2019
c = Counter()
current = int(s[len(s)-1])
c[0]+=1
c[current]+=1

for i in range(len(s)-2, -1,-1):
    current = mod_add(current, mod_mul(int(s[i]), mod_pow(10, len(s)-i-1)))
#    print(current)
    c[current%p] += 1

#print(c)
res = 0
for k in c.values():
    res += k*(k-1)//2

print(res)