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

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x = tuple(permutations(seq, D))
infty=100000
def main():
    #print(x)
    ans = infty
    for cand in x:
        cnt = 0
        G=G2
        for ind in cand:
            probpoint = (ind + 1) * 100
            if G<=0:
                break
            if G <= probpoint * (probs[ind][0] - 1):
                cnt = cnt + ceil(G / probpoint)
                G=G-probpoint*ceil(G / probpoint)
            else:
                cnt=cnt+probs[ind][0]
                G=G-(probpoint * probs[ind][0]+probs[ind][1])
        ans=min(ans,cnt)
    print(ans)

if __name__=='__main__':
    main()



### FIXED CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x=[]
for i in range(0,D+1):
    l=combinations(seq,i)
    for j in l:
        x.append(j)
x=tuple(x)
#print(x)
infty=100000
#print(x)
ans = infty
for cand in x:
    cnt = 0
    G=G2
    l=[0]*D
    for ind in cand:
        probpoint = (ind + 1) * 100
        G=G-(probpoint * probs[ind][0]+probs[ind][1])
        cnt = cnt + probs[ind][0]
        l[ind]=1
    #print(l,G,cnt)
    for i in range(D-1,-1,-1):
        if G<=0:
            break
        elif l[i]==0:
            probpoint = (i + 1) * 100
            num=ceil(G/probpoint)
            if num<probs[i][0]:
                G=G-num*probpoint
                cnt=cnt+num
            #print(cnt)
            break
    if G<=0:
        ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

def is_ok(a, b, c):
    if a < b + c:
        if b < c + a:
            if c < a + b:
                return True
    return False


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

    ans = 0
    for i, a in enumerate(l_list):
        for j, b in enumerate(l_list[i+1:]):
            for k, c in enumerate(l_list[i+1+j+1:]):
                # if i == j or j == k or k == i:
                #     continue
                if is_ok(a, b, c):
                    ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect


def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    l_list.sort()

    ans = 0
    for i, a in enumerate(l_list):
        for j, b in enumerate(l_list[i+1:]):
            x = a + b
            temp = bisect.bisect_left(l_list, x)
            ans += temp - (i + 1 + j + 1)
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = deque([(Dh, Dw)])
    while True:
        h, w = q.pop()
        # print('({}, {}) = {}'.format(h, w, ans))
        if h == Ch and w == Cw:
            print(ans)
            return True
        if not type(M[h][w]) == int:
            M[h][w] = ans
            for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= h+dh < H and 0 <= w+dw < W and M[h+dh][w+dw] == '.':
                    q.append((h+dh, w+dw))
        if len(q) == 0:
            # for h in range(H):
            #     print(M[h])
            f = False
            for h in range(H):
                for w in range(W):
                    if M[h][w] != '.':
                        continue
                    for i, j in [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-2, 1), (-1, 1), (1, 1), (2, 1), (-2, 0), (2, 0), (-2, -1), (-1, -1), (1, -1), (2, -1), (-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2)]:
                        if 0 <= h+i < H and 0 <= w+j < W and M[h+i][w+j] == ans:
                            f = True
                            # print('warp to ({}, {})'.format(h, w))
                            q.append((h, w))
            if f:
                ans += 1
            else:
                print(-1)
                return True

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 2019

    S = input()[::-1]
    N = len(S)
    nums = [0] * N
    for i in range(N):
        nums[i] = int(S[i])
    if N < 4:
        print(0)
        return

    R = [0] * 2019
    R[0] = 1 # '' の分
    t = 0
    for i in range(N):
        t += nums[i] * (10**i)
        t %= 2019
        R[t] += 1
    ans = 0
    for r in R:
        ans += r*(r-1)//2
    print(ans)
    




    

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 2019

    S = input()[::-1]
    N = len(S)

    if N < 4:
        print(0)
        return

    R = [0] * 2019
    R[0] = 1 # '' の分
    t = 0
    b = 1
    for c in S:
        t += int(c) * b
        t %= 2019
        R[t] += 1
        b *= 10
        b %= 2019
    ans = 0
    for r in R:
        ans += r*(r-1)//2
    print(ans)
    




    

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())

table = [0] * (n + 1)
    
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        table[j] += j


print(sum(table))

### FIXED CODE ###

n = int(input())

table = [0] * (n + 1)
    
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        table[j] += j


print(sum(table))
### BUGGY CODE ###

from collections import defaultdict

n = int(input())

nums = list(map(int, input().split()))

dic = defaultdict(int)
for num in nums:
    dic[num] += 1 


answers = []
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    dic[c] += dic[b]
    dic[b] = 0

    answer = 0
    for i, v in dic.items():
        answer += i * v

    answers.append(answer)

for answer in answers:
    print(answer)

### FIXED CODE ###

from collections import Counter

n = int(input())

nums = tuple(map(int, input().split()))

count = Counter(nums)
s = sum(nums)

answers = []
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    s = s + (c - b) * count[b]
    count[c] += count[b]
    count[b] = 0
    answers.append(s)
    
for answer in answers:
    print(answer)
### BUGGY CODE ###

N, K = list(map(int, input().split(" ")))

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

ans = False

cnt = 0
prev_len = 0
prepre_len = 0

while(1):
    if K in A:
        ans = True
        break
        
    
     
    if cnt == 0:
        for i in range(len(A)-1):
            for j in range(i+1, len(A)):
                tmp = abs(A[i] - A[j])
#                 print(tmp)
                if tmp not in A:
                    A.append(tmp)
                    
    else :
        for i in range(len(A)-1):
            for j in range(prepre_len, len(A)):
                tmp = abs(A[i] - A[j])
#                 print(tmp)
                if tmp not in A:
                    A.append(tmp)
                    
    if len(A) == prev_len:
        ans = False
        break
                    
#     print(A)
    
    prepre_len = prev_len
    prev_len = len(A)
    cnt += 1
    
    
if ans == True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N, K = list(map(int, input().split(" ")))

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

ans = False

A = sorted(A)

key = 99999999999999
    
if A[-1] < K:
    ans = False

else:
    for i in range(2, A[0]+1):
        key_flag = True
        for a in A:
            if a % i !=0:
                key_flag = False
                break
                
        if key_flag == True:
            key = i
            break

    if key_flag == False:
        ans = True
#         print(1)
    elif K % key == 0:
        ans = True
#         print(2)
    else:
#         print(3)
        ans = False           
    
if ans == True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())

a = list(map(int,input().split()))
g = max(a)
num = []
ans = 0
for i in range(n):
    value = a[i]
    if value >= n - (i+1):
        continue
    cnt = 1
    for j in range((i+value+1),n):
        if cnt == a[j] :
            ans += 1
        elif cnt > g:
            break
        cnt += 1

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ct = Counter(num)

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    if(ct[scan] != 0):
        ans += ct[scan]

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

l,r=map(int,input().split())
m=l*r%2019
for i in range(l,r):
    for j in range(i+1, r+1):
        m=min(m,i*j%2019)
print(m) 

### FIXED CODE ###

from itertools import combinations as f
l,r=map(int,input().split())
s=set(map(lambda x:x%2019,range(l,r+1)[:2019]))
print(min([i*j%2019 for i,j in f(s,2)]))
### BUGGY CODE ###

import numpy as np
from numba import jit
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = np.array(list(map(int, input().split())), dtype='i4')
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))
LR = np.array(LR, dtype='i4')
ANS = np.zeros(Q, dtype='i4')

# @njit(cache=1)
@jit('void(i4[:],i4,i4)', nopython=True)
def ftadd(ary, i, a):
    i += 1
    n = len(ary)
    while i < n:
        ary[i] += a
        i += i & -i


# @njit(cache=1)
@jit('i4(i4[:],i4)', nopython=True)
def ftsum(ary, i):
    i += 1
    ret = 0
    n = len(ary)
    while i > 0:
        ret += ary[i]
        i -= i & -i
    return ret


# @njit(cache=1)
@jit('void(i4[:], i4[:,:],i4[:],i4,i4)')
def solve(ANS, LR, C, N, Q):
    memo = -np.ones(N, dtype='i4')
    ST = np.zeros((N,2), dtype='i4')
    nst = 0
    for i in range(N):
        c = C[N-1-i]
        if memo[c-1] >= 0:
            ST[nst] = (N-i-1, memo[c-1])
            nst += 1
        memo[c-1] = N-i-1
    ST = ST[:nst]
    # ST.sort(reverse=True)
    LR = LR[np.argsort(LR[:,0])[::-1]]
    # ans = np.array(Q, dtype='i4')
    ft = np.zeros(N+1, dtype='i4')
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j,0] >= l:
            ftadd(ft, ST[j,1], 1)
            j += 1
        ANS[i] = r - l + 1 - ftsum(ft, r)
    # return ans

if __name__ == "__main__":
    solve(ANS, LR, C, N, Q)
    print('\n'.join(map(str, ANS.tolist())))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))


class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret


def solve():
    memo = [-1] * N
    ST = []
    nst = 0
    for i, c in enumerate(C[::-1]):
        if memo[c-1] >= 0:
            ST.append((N-i-1, memo[c-1]))
            nst += 1
        memo[c-1] = N-i-1
    # ST.sort(reverse=True)
    LR.sort(reverse=True, key=lambda x:x[0])
    ans =[0 for _ in range(Q)]
    ft = FenwickTree(N+1)
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j][0] >= l:
            ft.add(ST[j][1], 1)
            j += 1
        ans[i] = r - l + 1 - ft.sum(r)
    return ans

if __name__ == "__main__":
    print('\n'.join(map(str, solve())))
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        else:
            k = i
            while h2[k][0] == h:
                if c != 0 or h2[k][1] != 0:
                    ans = min(ans,c+h2[k][1])
                k += 1
                if k >= len(h2): break

        if i >= len(h2): break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = [INF] * 10000

    for i in range(1,2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        if h1[dif] > tc: h1[dif] = tc

    ans = h1[0]

    for i in range(1,2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        if dif == 0:
            ans = min(ans,tc)
        else:
            ans = min(ans,h1[dif]+tc)

    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

def f(i,j,k):
    return i+j*(N+1)+k*(N+1)**2

N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
    
dp=[0]*(N+1)**3
dp[1]=N
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k<=0 or i+j+k>N:
                continue
            dp[f(i,j,k)]=(i*dp[f(i-1,j,k)]+j*dp[f(i+1,j-1,k)]+k*dp[f(i,j+1,k-1)]+N)/(i+j+k)

print(dp[f(cnt[1],cnt[2],cnt[3])])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
aaa=cnt[1]
bbb=cnt[2]
ccc=cnt[3]

dp=[[[0]*(N+1) for j in range(bbb+ccc+1)] for i in range(ccc+1)]

for k in range(ccc+1):
    for j in range(bbb+ccc-k+1):
        for i in range(N-k-j+1):
            tmp=i+j+k
            if tmp==0:
                continue
            else:
                dp[k][j][i]=N/tmp
                if i>0:
                    dp[k][j][i]+=i*dp[k][j][i-1]/tmp
                if j>0:
                    dp[k][j][i]+=j*dp[k][j-1][i+1]/tmp
                if k>0:
                    dp[k][j][i]+=k*dp[k-1][j+1][i]/tmp
                
print(dp[ccc][bbb][aaa])
### BUGGY CODE ###

N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))


### FIXED CODE ###

N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))
### BUGGY CODE ###

import sys

def calc():
    while 1:
        n = int(raw_input())
        if n == 0:
            break
        a = 0
        b = 0
        ans = map(int, raw_input().split())
        while n > 0:
            if ans[0] > ans[1]:
                a += ans[0] + ans[1]
            elif ans[1] < ans[0]:
                b += ans [0] + ans[1]
            else:
                a += ans[0]
                b += ans[1]
        print a, b
    
if __name__ == '__main__':
    calc()

### FIXED CODE ###

import sys

def calc():
    while 1:
        n = int(raw_input())
        if n <= 0:
            break
        a = 0
        b = 0
        while n > 0:
            ans = map(int, raw_input().split())
            if ans[0] > ans[1]:
                a += ans[0] + ans[1]
            elif ans[0] < ans[1]:
                b += ans [0] + ans[1]
            else:
                a += ans[0]
                b += ans[1]
            n -= 1
        print a, b
        
    
if __name__ == '__main__':
    calc()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,q = map(int,input().split())
s = input()
lr = []
for _ in range(q):
    lr.append(list(map(int,input().split())))

count = []
for i in range(0,n-1):
    if s[i] == 'A' and s[i+1] == "C":
        count.append(i+1)


for slr in lr:
    l = slr[0]
    r = slr[1]
    res = 0
    for c in count:
        if c >= l and c < r:
            res += 1
    print(res)




### FIXED CODE ###

import sys
from itertools import accumulate
input = sys.stdin.readline

n,q = map(int,input().split())
s = input()
lr = []
for _ in range(q):
    lr.append(list(map(int,input().split())))

count = [0]
for i in range(0,n-1):
    if s[i] == 'A' and s[i+1] == "C":
        count.append(1)
    else:
        count.append(0)
count.append(0)

flag = list(accumulate(count))

for slr in lr:
    l = slr[0]
    r = slr[1]
    print(flag[r-1] - flag[l-1])
### BUGGY CODE ###

l,r = map(int,input().split())
ans = l*(l+1)
for i in range(l,r):
    for j in range(i+1,r+1):
        mod = (i*j)%2019
        if mod < ans:
            ans = mod
print(ans)

### FIXED CODE ###


l,r = map(int,input().split())
ans = l*(l+1)
if int(l/2019) < int(r/2019):
    print(0)
else:
    for i in range(l,r):
        for j in range(i+1,r+1):
            mod = (i*j)%2019
            if mod < ans:
              ans = mod
            if ans == 0:
                break
    print(ans)
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
sum = 0
for x in range(1, k + 1):
	for y in range(1, k + 1):
		for z in range(1, k + 1):
			sum += gcd(x, y, z)
print(sum)

### FIXED CODE ###

import math

k = int(input())
two = []
total = 0
for x in range(1, k + 1):
	for y in range(1, k + 1):
		two.append(math.gcd(x, y))

for z in range(1, k + 1):
	for i in two:
		total += math.gcd(z, i)
print(total)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
reached=[[0]*W for i in range(H)]
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
        ans=max(ans,reached[y][x])
print(ans)


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
reached=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
            reached[i][j]=0
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=-1:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
        ans=max(ans,reached[y][x])
print(ans)