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

N,K,C = (int(i) for i in input().split())
S = str(input())

L = [-1] * K
R = [-1] * K
S_index = 0
count = 0
while count < K:
  if S[S_index] == "o":
    L[count] = S_index
    count += 1
    S_index += C+1
  else:
    S_index += 1

S_index = N-1
count = 0
while count < K:
  if S[S_index] == "o":
    R[count] = S_index
    count += 1
    S_index -= C+1
  else:
    S_index -= 1

for l in L:
  if l in R:
    print(l+1)


### FIXED CODE ###

N,K,C = (int(i) for i in input().split())
S = str(input())

L = [-1] * K
R = [-1] * K
S_index = 0
count = 0
while count < K:
  if S[S_index] == "o":
    L[count] = S_index
    count += 1
    S_index += C+1
  else:
    S_index += 1

S_index = N-1
count = 0
while count < K:
  if S[S_index] == "o":
    R[count] = S_index
    count += 1
    S_index -= C+1
  else:
    S_index -= 1

R.reverse()
for l,r in zip(L,R):
  if l == r:
    print(l+1)
### BUGGY CODE ###

N,W = map(int,input().split())
INF = 10**12
V = 1000 * N
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

#DP[n][v]: n番目までの品物で 価値vの品物を選んだ場合の重さの最小
DP = [[INF]*(V+1) for _ in range(N+1)]
for n in range(N+1):
    DP[n][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        wi,vi = Data[n]
        if v >= vi:
            DP[n][v] = min(DP[n][v],DP[n-1][v-vi]+wi)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

ans = 0
for  v in range(V+1):
    if DP[N][v] <= W:
        ans = v
print(ans)

### FIXED CODE ###

N,W = map(int,input().split())
INF = 10**12
V = 1000 * N
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

DP = [[INF]*(V+1) for _ in range(N+1)]
for n in range(N+1):
    DP[n][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        wi,vi = Data[n]
        if v >= vi:
            DP[n][v] = min(DP[n][v],DP[n-1][v-vi]+wi)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

ans = 0
for  v in range(V+1):
    if DP[N][v] <= W:
        ans = v
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ball = []
s = 0

for i in range(n-1, (n-1)//2, -1):
    ball.insert(0, a[i])
for i in range((n-1)//2, -1, -1):
    for j in range(len(ball)):
        if (j+1) % (i+1) == 0:
            s += ball[j]

    s = s % 2
    if a[i] == s:
        ball.insert(0, 0)
    else:
        ball.insert(0, 1)
ans = ""
count = 0
for i in range(n):
    if ball[i] == 1 and i < n-1:
        ans += str(i+1) + ""
        count += 1
    elif ball[i] == 1 and i==n-1:
        ans += str(i+1)
        count += 1
if count > 0:
    print(count)
    print(ans)
else:
    print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ball = [0 for i in range(n)]
count = 0 #ボールが入ってる箱の数
index = [] #ボールが入ってる番号

for i in range(n-1, -1, -1):
    balls = 0
    j = i
    while j +(i+1) < n:
        j += i + 1
        balls += ball[j]
    
    if a[i] != balls%2:
        ball[i] = 1
        count += 1
        index.append(i+1)
        
ans = ""
for i in range(len(index)):
    if i < len(index)-1:
        ans += str(index[i]) + " "
    else:
        ans += str(index[i])
print(count)
print(ans)
### BUGGY CODE ###

S = str(input())
Q = int(input())
query = [ input().split() for _ in range(Q) ]

for i in range(Q):
    if query[i][0] == str(1):
        S = S[::-1]
    elif query[i][0] == str(2):
        if query[i][1] == str(1):
            S = query[i][2] + S
        else:
            S = S + query[i][2]
print(S)


### FIXED CODE ###

from collections import deque
S = str(input())
Q = int(input())
query = [ input().split() for _ in range(Q) ]

tag = False
que = deque([S])

for i in range(Q):
    if query[i][0] == str(1):
        if tag == False:
            tag = True
        else:
            tag = False
    elif query[i][0] == str(2):
        if query[i][1] == str(1):
            if tag == False:
                que.appendleft(query[i][2])
            else:
                que.append(query[i][2])
        else:
            if tag == False:
                que.append(query[i][2])
            else:
                que.appendleft(query[i][2])
ans = "".join(que)
if tag == True:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

N = int(input())
A = set()
for i in range(N):
    A = A^{int(input())}
print(len(A))

### FIXED CODE ###

N = int(input())
A = set()
for i in range(N):
    A ^= {input()}
print(len(A))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 30
ans = 0
from bisect import bisect_left as bl, bisect_right as br
def sub(k):
    tmp = pow(2, k)
    bb = [item%(tmp*2) for item in b]
    bb.sort()
    ans = 0
    for item in a:
        aa = item%(tmp*2)
        if aa<=tmp:
            num = br(bb, tmp*2-1-aa) - bl(bb, tmp-aa)
        else:
            num = br(bb, tmp*2-1-aa) + (n - bl(bb, tmp*3-aa))
        ans += num
        ans %= 2
    return ans%2
    
for k in range(l):
    # i桁目を求める
    if sub(k):
        ans += pow(2, k)
print(ans)


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
r = 0
while p:
    s = {
        (k, l) for i, j in p
        for k in range(i - 1, i + 2) for l in range(j - 1, j + 2)
        if 0 <= k < h and 0 <= l < w and (k + l + i + j) % 2 == 1
        and a[k][l] == '.'
        }
    if s:
        r += 1
    for i, j in s:
        a[i][j] = '#'
    p = s
print(r)


### FIXED CODE ###

h, w = map(int, input().split())
a = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(h)] + [['#'] * (w + 2)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)
### BUGGY CODE ###

from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
c = dic.most_common()
mod = 10**9 + 7

ans = 0
d = []
append = d.append
for x in c:
    if x[1] == 1:
        break
    else:
        append(x[1])
b = len(c)-len(d)

ls =list(product([0, 1], repeat=len(d)))

for x in ls:
    num = 1
    for z, y in zip(d, x):
        if y == 1:
            num = (z*num)%mod
    ans = (ans + num*(2**b))%mod
print(ans-1)

### FIXED CODE ###

from collections import Counter
from itertools import product
 
N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 1
for x in dic:
    ans = ans*(dic[x]+1)%mod
print(ans-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 23 21:51:02 2019

@author: Yamazaki Kenichi
"""

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

ans = [[-1 for i in range(N+1)]]
ans[0][N] = 0
for i in range(1,W+1):
    tmp = -1
    maxv = ans[-1][N]
#    print('aa',maxv)
    for j in range(N):
#        print(i,j,A[j][0],maxv,ans[i -A[j][0]][j])
#        print(i,j,A[j],i -A[j][0],ans[-1])
        if i-A[j][0] >= 0 and ans[i-A[j][0]][j] == -1 and ans[i-A[j][0]][N] + A[j][1] > maxv:
            maxv = ans[i-A[j][0]][N] + A[j][1]
            tmp = j
#            print('maxv',maxv,'tmp',tmp)
    if tmp != -1:
        ans.append(ans[-A[tmp][0]][:])
        ans[i][tmp] = 1
    else:
        ans.append(ans[-1][:])
    ans[i][N] = maxv
#    print(ans[i][N])
#    print(ans[i])
print(ans[W][N])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 23 21:51:02 2019

@author: Yamazaki Kenichi
"""

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

ans = [[-1 for i in range(N+1)]]
ans[0][N] = 0
for i in range(1,W+1):
    tmp = -1
    maxv = ans[-1][N]
#    print('aa',maxv)
    for j in range(N):
#        print(i,j,A[j][0],maxv,ans[i -A[j][0]][j])
#        print(i,j,A[j],i -A[j][0],ans[-1])
        if i-A[j][0] >= 0 and ans[i-A[j][0]][j] == -1 and ans[i-A[j][0]][N] + A[j][1] > maxv:
            maxv = ans[i-A[j][0]][N] + A[j][1]
            tmp = j
#            print('maxv',maxv,'tmp',tmp)
    if tmp != -1:
        ans.append(ans[-A[tmp][0]][:])
        ans[i][tmp] = 1
    else:
        ans.append(ans[-1][:])
    ans[i][N] = maxv
#    print(ans[i][N])
#    print(ans[i])
print(ans[W][N])
### BUGGY CODE ###

a, b, c, d = map(int, input().split())

t_hp = a
a_hp = c

while t_hp > 0 and a_hp > 0:
    t_hp = a - d
    a_hp = c - b

if a_hp <= 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a, b, c, d = map(int, input().split())

while a > 0 and c > 0:
    a = a - d
    c = c - b

if c <= 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[j] + abs(inputs[j] - inputs[i]) for j in range(start, i))

print(dp[-1])


### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()

print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

def gcd(n, m):
    if(m): return gcd(m, n%m)
    else: return n

def lcm(n, m):
    return n // gcd(n, m) * m

LCM = a[0]
for i in range(1, n):
    LCM = lcm(a[i], LCM)

res = 0
MOD = 1000000007
for i in range(n):
    res = (res + LCM//a[i]) % MOD
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
def gcd(n, m):
    if(m): return gcd(m, n%m)
    else: return n
 
def lcm(n, m):
    return n // gcd(n, m) * m
 
LCM = a[0]
for i in range(1, n):
    LCM = lcm(a[i], LCM)
 
res = 0
MOD = 1000000007
for i in range(n):
    res += LCM//a[i]
    
print(res % MOD)
### BUGGY CODE ###

def ck(a,b,arr):
  if sum(arr[a:b]) == b - a:
    return 1
  else:
    return 0

N,M=map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]
List_2 = [0] * M
arr = [1] * N

for i in range(M):
  a = List[i][1]
  b = List[i][0]
  List_2[i] = [a,b]
  
List_2.sort()
  
for i in range(M):
  a = List_2[i][1]
  b = List_2[i][0]

  hantei = ck(a,b,arr)
  if hantei == 1:
    arr[b-1] = 0
  
print(int(N - sum(arr)))

### FIXED CODE ###

def ck(a,b,arr):
  if arr >= a and arr < b:
    return 0
  else:
    return 1

N,M=map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]
List_2 = [0] * M
arr = 0
cnt = 0

for i in range(M):
  a = List[i][1]
  b = List[i][0]
  List_2[i] = [a,b]
  
List_2.sort()
  
for i in range(M):
  a = List_2[i][1]
  b = List_2[i][0]

  hantei = ck(a,b,arr)
  if hantei == 1:
    arr = b-1
    cnt += 1
  
print(int(cnt))
### BUGGY CODE ###

N = int(input())
n=0
num=[]
for i in range(N):
    s=list(str(N-i))
    for j in range(len(s)):
        n+=int(s[j])
    num.append(n)
    n=0
print(max(num))        
        


### FIXED CODE ###

def f(s):
    p=0
    for i in str(s):
        p+=int(i)
    return p
N=int(input())
i=1
ans=f(N)
while N>=10**i:
    p=f((N//10**i)*(10**i)-1)
    ans=max(ans,p)
    i+=1
print(ans)
### BUGGY CODE ###

s=input()

a=0
ab=0
abc=0
q=0

#if s[0]=="A" :
#  a=1
#elif s[0]=="?":
#  a=1
#  q=1
#print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))

for i in range(len(s)):
  if s[i]=="A":
    a=(a+3**q)%(10**9+7)
  elif s[i]=="B":
    ab=(ab+a)%(10**9+7)
  elif s[i]=="C":
    abc=(abc+ab)%(10**9+7)
  elif s[i]=="?":
    abc=(abc*3+ab)%(10**9+7)
    
    ab=(ab*3+a)%(10**9+7)
    a=(a*3+3**q)%(10**9+7)
    q+=1
  #print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))
    
print(abc)


### FIXED CODE ###

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, Q = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
cnt = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
def EulerTour(v, p, c):
    for u in es[v]:
        if u != p:
            EulerTour(u, v, c+cnt[v])
    cnt[v] += c
EulerTour(1, 0, 0)
print(*cnt[1:])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, Q = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
cnt = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
def EulerTour(v, p, c):
    for u in es[v]:
        if u != p:
            EulerTour(u, v, c+cnt[v])
    cnt[v] += c
EulerTour(1, 0, 0)
print(*cnt[1:])
### BUGGY CODE ###

from itertools import combinations

n = int(input())
A = [0] + list(map(int,input().split()))

cnt = 0
combination = combinations(range(1, n+1), 2)
for comb in combination:
    x, y = comb[0], comb[1]
    if abs(x - y) == A[x] + A[y]:
        cnt += 1
print(cnt)


### FIXED CODE ###

from collections import defaultdict

n = int(input())
A = list(map(int, input().split()))

cnt = 0
d = defaultdict(int)
# j - i = Ai + Aj --> i + Ai = j - Aj
for i in range(n):
    cnt += d[i - A[i]]
    d[i + A[i]] += 1

print(cnt)
### BUGGY CODE ###

import sys

X, K, D = list(map(int, input().split()))

p = X
_p = 0
k = 0

if abs(p) > K*D:
    print(abs(p)-K*D)
    sys.exit()

if p < 0:
    for i in range(K):
        _p = p
        p += D
        k += 1
        if p > 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
elif p > 0:
    for i in range(K):
        _p = p
        p -= D
        k += 1
        if p < 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
else:
    if K % 2 == 0:
        print(0)
    else:
        print(D)


### FIXED CODE ###

import sys

X, K, D = list(map(int, input().split()))

p = X
_p = 0
k = 0

if abs(p) > K*D:
    print(abs(p)-K*D)
    sys.exit()

if p < 0:
    for i in range(K):
        _p = p
        p += D
        k += 1
        if p > 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
elif p > 0:
    for i in range(K):
        _p = p
        p -= D
        k += 1
        if p < 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
else:
    if K % 2 == 0:
        print(0)
    else:
        print(D)
### BUGGY CODE ###

from collections import deque
N,M=map(int,input().split())
B=[[] for i in range(N)]

for i in range(M):
  a,b=map(int,input().split())
  B[a-1].append(b-1)
  B[b-1].append(a-1)
  
visited=[]
d = deque()
ans=[-1]*N
now=0
d.append(0)
while d:
  c=d.popleft()
  visited.append(c)
  for e in B[c]:
    if e in visited:
      continue
    if e in d:
      continue
    
    d.append(e)
    ans[e]=c
    
if ans.count(-1)!=1:
  print("No")
else:
  print("Yes")
  for i in range(1,N):
    print(ans[i]+1)
  
  

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
B=[[] for i in range(N)]

for i in range(M):
  a,b=map(int,input().split())
  B[a-1].append(b-1)
  B[b-1].append(a-1)
  
visited=[0]*N
d = deque()
ans=[-1]*N
d.append(0)
visited[0]=1
while d:
  c=d.popleft()
  for e in B[c]:
    if visited[e]:
      continue
      
    d.append(e)
    visited[e]=1
    ans[e]=c
    
print("Yes")
for i in range(1,N):
  print(ans[i]+1)
### BUGGY CODE ###

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

a_lst = list(map(int, input().split(" ")))

# previousの値を取っておいて真に掛け算した評定が高かったかを判定
previous = 1
for i in range(k):
    previous *= a_lst[i]
for i in range(k, n):
    now = previous / a_lst[i - k] * a_lst[i]
    if now > previous:
        print("Yes")
    else:
        print("No")
    previous = now


### FIXED CODE ###

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

a_lst = list(map(int, input().split(" ")))

for i in range(k, n):
    if a_lst[i] > a_lst[i - k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    DP[1], DP[0] = DP[0], DP[1]
    for j in range(13):
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
               DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)


### FIXED CODE ###

S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
               DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c <= max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))
### BUGGY CODE ###

from math import sqrt
N = int(input())

for n in range(1, N+1):
    count = 0
    for x in range(1, int(sqrt(n))):
        for y in range(x,int(sqrt(n))):
            for z in range(y, int(sqrt(n))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    if len(set([x, y, z])) == 3:
                        count += 6
                    elif len(set([x, y, z])) == 2:
                        count += 3
                    elif len(set([x, y, z])) == 1:
                        count += 1
    print(count)

### FIXED CODE ###

from math import sqrt
N = int(input())
ans = [0] * (N+1)

for x in range(1, int(sqrt(N)) + 2):
    for y in range(1,int(sqrt(N)) + 2):
        for z in range(1, int(sqrt(N)) + 2):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n <= N:
                ans[n] += 1

for i in range(1, len(ans)):
    print(ans[i])
### BUGGY CODE ###

import bisect
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for t in reversed(range(1, 31)):
    for i in reversed(range(n)):
        if memo[a[i]]== 0:
            continue
        front = bisect.bisect_left(a, (1 << t) - a[i])
        back = bisect.bisect_right(a, (1 << t) - a[i])
        if front == back:
            continue
        if a[front] == a[i] and memo[a[i]] <= 1:
            continue
        if memo[a[front]] >= 1:
            memo[a[front]] -= 1
            memo[a[i]] -= 1
            count += 1

print(count)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if (memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 0 and (1 << (len(bin(a[i])) - 2)) - a[i] != a[i]) or memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 1:
        memo[a[i]] -= 1
        memo[(1 << (len(bin(a[i])) - 2)) - a[i]] -= 1
        count += 1

print(count)
### BUGGY CODE ###

n = int(input()) 
a = list(map(int, input().split()))


z = 1
for i in range(0, n):
  z = z * a[i]


if z > 1000000000000000000:
  print("-1")
else:
  print(z)


### FIXED CODE ###

n = int(input()) 
a = list(map(int, input().split()))

y = 1
q = 1
z = 1
for i in range(0, n):
  if a[i] == 0:
    q = 0

for i in range(0, n):
  z = z * a[i]
  if z > 1000000000000000000:
    y = -1
    break
 
if q == 0:
  print(0)
elif z <= 1000000000000000000:
  print(z)
else:
  print("-1")
### BUGGY CODE ###

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

expect_list = [((1+yokolist[i])/2) for i in range(n)]

#print(expect_list)

answer = 0
for j in range(n-k+1):
    l = expect_list[j:j+k]
    p = sum(l)
    if p > answer:
       answer = p

print(answer)

### FIXED CODE ###

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

expect_list = [((1+yokolist[i])/2) for i in range(n)]

#print(expect_list)

answer = 0
l = expect_list[0:k]
p = sum(l)
for j in range(n-k+1):
    if p > answer:
       answer = p
    if j != n-k:
        p = p - expect_list[j] + expect_list[k+j]

print(answer)