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

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():    
    s=list(input())
    N=len(s)
    i=0
    ans=0
    if N>=3:
        if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
            s[i],s[i+1],s[i+2]='B','C','A'
            i+=1
            ans+=1
        while True:
            while True:
                i+=1
                if i >= N-2:
                    print(ans)
                    exit()
                if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
                    break
            s[i],s[i+1],s[i+2]='B','C','A'
            if i!=0 and s[i-1]=='A':
                i-=2
            else:
                i+=1
            ans+=1
    else:
        print(ans)
        
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    s=input()
    s2=list(s.replace('BC','D'))
    N=len(s2)
    ans=0
    c=0
    for i in range(N):
        if s2[i]=='A':
            c+=1
        elif c!=0 and s2[i]=='D':
            ans+=c
        else:
            c=0
    print(ans)

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

import math
N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N > math.ceil(K // 2):
                N = abs(N-K)
        print(N)

### FIXED CODE ###

import math
N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N >= math.ceil(K / 2):
                N = abs(N-K*(N//K+1))
        print(N)
### BUGGY CODE ###

def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7

    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[(10 * i + j) % 13 for j in range(10)] for i in range(13)]
    r13 = range(13)
    for l in s:
        if l == '?':
            for i in r13:
                q = table1[i]
                for k in pre[i]:
                    table2[k] += q
        else:
            for i in r13:
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[((10 * i + j) % 13) for j in range(10)] for i in range(13)]

    for l in s:
        for i in range(13):
            q = table1[i] % mod
            if q == 0:
                continue
            if l == '?':
                for k in pre[i]:
                    table2[k] += q
            else:
                k = (10 * i + int(l)) % 13
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


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

n = int(input())
c = input()

w = []
r = []
for i in range(n):
  if c[i] == 'W':
    w.append(i+1)
  else:
    r.append(i+1)

w_len = len(w)
r_len = len(r)
if w_len == 0 or r_len == 0:
  print(0)
  exit(0)

count = 0
for i in range(n):
  tmp = w[i]
  w[i] = r[r_len-i-1]
  r[r_len-i-1] = tmp
  count += 1
  
  if max(r) < min(w):
    print(count)
    exit(0)
print(count)

### FIXED CODE ###

n = int(input())
c = input()

w = []
r = []
for i in range(n):
  if c[i] == 'W':
    w.append(i+1)
  else:
    r.append(i+1)

w_len = len(w)
r_len = len(r)
if w_len == 0 or r_len == 0:
  print(0)
  exit(0)

if w_len < r_len:
  search = w_len
else:
  search = r_len

w_min = w[0]
r_max = r[r_len-1]

if r_max < w_min:
  print(0)
  exit(0)

count = 0
for i in range(search):
  tmp = w[i]
  w[i] = r[r_len-i-1]
  r[r_len-i-1] = tmp
  count += 1
  
  if w_len > count and (r_len-count-1) >= 0:
    w_min = w[count]
    r_max = r[r_len - count - 1]
  else:
    w_min = w[w_len-1]
    r_max = r[0]
    
  if r_max < w_min:
    print(count)
    exit(0)
print(count)
### BUGGY CODE ###

lines = []
for i in range(2):
    lines.append(input())
num = int(lines[0])

out = 1
split = lines[1].split()
for i in range(num):
    out = int(split[i]) * out 
if out > 1000000000000000000:
    out = - 1    
print(out)

### FIXED CODE ###

lines = []
for i in range(2):
    lines.append(input())
num = int(lines[0])

out = 1
split = lines[1].split()
if "0" in split:
    out = 0
for i in range(num):
    out = int(split[i]) * out 
    if out > 1000000000000000000:
        out = - 1    
        break
print(out)
### BUGGY CODE ###

n = int(input())

l753 = ['3', '5', '7']
ans = 0

for i in range(n+1):
    l = list(str(i))
    if all((j in l753) for j in l) and len(set(l)) == 3:
        ans += 1

print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())

def bfs(s):
    que = deque()
    que.append(s)
    cnt = 0
    while que.__len__() != 0:
        s = que.popleft()
        for ds in '753':
            ss = s + ds
            if int(ss) > N:
                continue
            if all(ss.count(i) > 0 for i in '753'):
                cnt += 1
            que.append(ss)
    return cnt

ans = 0
ans += bfs('3')
ans += bfs('5')
ans += bfs('7')

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

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = [0] * H
    Wlist = [0] * W
    hwset = [set() for _ in range(H)]

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hwset[h-1].add(w)


    hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]

    flag = False
    for h in hmax:
        for w in wmax:
            if w+1 not in hwset[h]:
                flag = True
                break

    if flag:
        print(Hlist[h] + Wlist[w])
    else:
        print(Hlist[h] + Wlist[w] - 1)





if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = collections.defaultdict(int)
    Wlist = collections.defaultdict(int)
    hw = []

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hw.append([h, w])

    #hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    #wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]

    Hlist = sorted(Hlist.items(), key=lambda x: x[1], reverse=True)
    Wlist = sorted(Wlist.items(), key=lambda x: x[1], reverse=True)

    hmaxset = set()
    wmaxset = set()

    maxH = Hlist[0][1]
    for k, v in Hlist:
        if v != maxH:
            break
        else:
            hmaxset.add(k)

    maxW = Wlist[0][1]
    for k, v in Wlist:
        if v != maxW:
            break
        else:
            wmaxset.add(k)


    flag = False
    count = 0
    for hh in hw:
        h = hh[0] - 1
        w = hh[1] - 1
        if h in hmaxset and w in wmaxset:
            count += 1

    lenhmax = len(hmaxset)
    lenwmax = len(wmaxset)

    if count != lenhmax * lenwmax:
        flag = True

    if flag:
        print(maxH + maxW)
    else:
        print(maxH + maxW - 1)





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

N = int(input())
P = list(map(int, input().split()))

count = 0
for i in range(N):
  if N == 1:
    count = 1
    break
  dame = False
  for j in range(i):
    if P[i] > P[j]:
      dame = True
      break
  if not dame:
    count += 1

print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

count = 0
m = P[0]
for i in range(N):
  if (m >= P[i]):
    count += 1
    m = P[i]
print(count)
### BUGGY CODE ###

from collections import Counter
n=int(input())
s = [0]*n
for i in range(n):
    s[i]=input()
d = Counter(s)
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()
for i in max_k_list:
    print(i)


### FIXED CODE ###

n=int(input())
d={}
for i in range(n):
    tmp = input()
    if tmp in d:
        d[tmp]+=1
    else:
        d[tmp]=1
max_k_list=[]
max_d = max(d.values())
for k,v in d.items():
    if v == max_d:
        max_k_list.append(k)
max_k_list.sort()
for i in max_k_list:
    print(i)
### BUGGY CODE ###

R,G,B,N = map(int, input().split())
cnt = 0
for i in range(N//R+1):
    for j in range(N//G+1):
       r,g = i*R, j*G
       if (N-r-g)%B!=0 or r+g > N: continue
       cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0

a = max(R, G, B)
if a == R:
  b = max(G, B)
elif a == G:
  b = max(B, R)
else:
  b = max(R, G)
c = min(R, G, B)
for i in range(N//a+1):
  for j in range((N-a*i)//b+1):
    if ((N-a*i)-b*j)%c == 0:
      ans += 1
print(ans)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[[None]*(W+2)]+\
  [[None] + [i=="." for i in input()] + [None] for _ in range(H)] + \
  [[None]*(W+2)]
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==False:
            q.append((i,j))
if len(q)==H*W:
    print(0)
    import sys
    sys.exit()
for k in range(2000):
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=False
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=False
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=False
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=False
            r.append((i,j+1))
    q=[i for i in r]
    r=[]
    if q==[]:
        break
    cnt+=1
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

import itertools
n = int(input())

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


aas = list(itertools.combinations(a,2))
m = len(aas)

x = 0
for i in range(m):
    x += ((aas[i][0] ^ aas[i][1]) % (10**9 + 7))
    x %= 10**9 + 7

print(x)


### FIXED CODE ###

n = int(input())

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

ans = 0
for i in range(60):
    k = 1 << i
    i_1 = sum([k & a for a in ass]) >> i
    ans += i_1 * (n - i_1) << i
    ans = ans % ((10**9) + 7)

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

N,K=map(int,input().split())
a=list(map(int,input().split()))
Tmp=0
for i in range(N-K+1):
  s=sum(a[i:i+K])
  if s>Tmp:
    Tmp=s
ans=(Tmp+K)/2
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
s=[0]
for i in range(n):
  s.append(a[i]+s[-1])
for i in range(n-k+1):
  tot=s[i+k]-s[i]
  ans=max((tot+k)/2,ans)
print(ans)
### BUGGY CODE ###

import sys

K = int(input())

if K>10**6 or K<1 :
    print(-1)
    sys.exit()

if K%2 == 0 or K%5 ==0:
    print(-1)
    sys.exit()
    
N = 7
count = 0
i = 1

while i:
    
    count += 1
    if N % K == 0:
        print(count)
        sys.exit()
    
    if count > K:
        print(-1)
        sys.exit()
    
    N = N*10 + 7

### FIXED CODE ###

K = int(input())

N = 0
count = -1

for i in range(K):
    N = (N*10+7)%K
    if N == 0:
        count = i+1
        break
    
print(count)
### BUGGY CODE ###

N = int(input())
lst = [int(i) for i in input().split()]
lst.insert(0, 0)
res = [0]
for i in range(1, N+1):
    t = lst[:]
    del(t[i])
    # if max(t) < 0:
    #     res.append(2 * abs(min(t)))
    # elif min(t) > 0:
    #     res.append(2 * maxt)
    # else:
    #     res.append(2 * (max(t) - min(t)))
    k = 0
    for i in range(1, len(t)):
        k += abs(t[i] - t[i-1])
    res.append(k + abs(t[-1]))

for i in range(1, N+1):
    print(res[i])


### FIXED CODE ###

import sys
for line in sys.stdin:
    if line == None or line == '\n':
        break
    line = line.rstrip()
    line = line.split(" ")
    if len(line) == 1:
        N = int(line[0])
        continue
    else:
        coordinates = line

        coordinates.insert(0, 0)
        coordinates.append(0)

        prev_coord = int(coordinates[0])
        total_cost = 0
        for i in range(1, len(coordinates)):
            total_cost += abs(int(coordinates[i]) - int(coordinates[i-1]))

        for i in range(1, len(coordinates) - 1):
            print(total_cost - abs(int(coordinates[i]) - int(coordinates[i - 1])) - abs(int(coordinates[i]) - int(coordinates[i + 1])) + abs(int(coordinates[i + 1]) - int(coordinates[i - 1])))
### BUGGY CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
c=[[False]*w for i in range(h)]
def f(x,y,t,p):
    if 0<=x<h and 0<=y<w:
        if p[x][y]==False:
            if s[x][y]=="#":
                if b[x][y]==False:
                    a[x][y]=0
                    b[x][y]=True
                    k=[[False]*w for i in range(h)]
                    f(x,y+1,1,k)
                    f(x+1,y,1,k)
                    f(x-1,y,1,k)
                    f(x,y-1,1,k)
            else:
                if a[x][y]>t and t<h+w:
                    a[x][y]=t
                    c[x][y]=True
                    f(x,y+1,t+1,p)
                    f(x+1,y,t+1,p)
                    f(x-1,y,t+1,p)
                    f(x,y-1,t+1,p)
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            f(i,j,0,c)
            break
print(max(max(i)for i in a))

### FIXED CODE ###

import numpy as np
from scipy.ndimage import distance_transform_cdt as d
h,w=map(int,input().split())
s=[[1 if i=="." else 0 for i in input()]for i in range(h)]
a=d(s,metric='taxicab')
print(a.max())
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()
LS = len(S)
dp = [[0] * 13 for _ in range(LS+1)]
dp[0][0] = 1

for k in range(LS):
    #prev = [x for x in dp]
    #dp = [0] * 13
    s = S[k]
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[k+1][(i*10+a)%13] += dp[k][i]
    dp[k+1] = [x % MOD for x in dp[k+1]]
print(dp[LS][5])

### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

s=input()
l=len(s)
mod=2019
x=[(int(s[i])*(pow(10,l-i-1)))%2019 for i in range(l)]
y=[0]*l
y[0]=x[0]%mod
for i in range(1,l):
  y[i]=(y[i-1]+x[i])%mod
cnt=y.count(0)
print(l-len(set(y))+cnt)

### FIXED CODE ###

def main():
  s=input()[::-1]
  l,mod=len(s),2019
  x=[0]*mod
  x[0]=1
  a,t=0,1
  for i in range(l):
    a = (a + int(s[i])*t) % 2019
    x[a]+=1
    t=(t*10)%mod
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

ans = 0
for i in range(N - K + 1):
    a = 0
    for j in range(K):
        a += (p[i+j] + 1) / 2
    ans = max(ans,a)

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(K):
    ans += p[i]
    tt = ans
for i in range(K,N):
    tt = tt+p[i]-p[i-K]
    ans = max(ans, tt)
print((ans + K)/2)
### BUGGY CODE ###

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

import fractions
from functools import reduce

def gcds(numbers):
  return reduce(fractions.gcd,numbers)

nm = 0

for i in range(n):
  t = gcds(lis[:i]+lis[i+1:])
  if nm < t:
    nm = t
print(nm)


### FIXED CODE ###

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

import fractions
from functools import reduce

def gcds(numbers):
  return reduce(fractions.gcd,numbers)
def gcd2(*numbers):
  return reduce(fractions.gcd,numbers)
  

mx = 0

lisgcd = [0]*n
rlisgcd = [0]*n

lisgcd[0] = lis[0]
rlisgcd[n-1] = lis[n-1]

for i in range(n-1):
  lisgcd[i+1] = gcd2(lisgcd[i],lis[i])
  
for i in range(n-2,-1,-1):
  rlisgcd[i] = gcd2(rlisgcd[i+1],lis[i])
  
for i in range(n):
  if i == 0:
    if mx < rlisgcd[1]:
      mx = rlisgcd[1]
  elif i == n-1:
    if mx < lisgcd[n-1]:
      mx = lisgcd[n-1]
  else:
    t = gcd2(lisgcd[i],rlisgcd[i+1])
    if mx < t:
      mx = t
print(mx)
### BUGGY CODE ###

x,k,d = list(map(int,input().split()))

xi = abs(x)
if abs(x) > d*k:
  m = min(abs(x+d*k),abs(x-d*k))
else:
  for i in range(k):
    xi -= d
    if xi <= 0:
      if (i+k) % 2 != 0:
        m = abs(xi)
      else:
        m = min(abs(xi+d),abs(xi-d))
      break
print(m)

### FIXED CODE ###

from math import ceil 
x,k,d = list(map(int,input().split()))

xi = abs(x)
if abs(x) > d*k:
  m = min(abs(x+d*k),abs(x-d*k))
else:
  n = ceil(xi / d)
  if (n+k) % 2 == 0:
    m = abs(xi-d*n)
  else:
    m = abs(xi-d*(n-1))
print(m)
### BUGGY CODE ###

n = int(input().strip())
ans = 0
for i in range(n):
    ans = ans + i
print(ans)


### FIXED CODE ###

import math
n = int(input().strip())
ans = (n*(n-1))//2

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

import  collections

H, W, M = map(int, input().split())

H_count = collections.defaultdict(set)
W_count = collections.defaultdict(set)
for m in range(M):
    h, w = map(int, input().split())
    H_count[h].add(w)
    W_count[w].add(h)

max_count = 0

for h, w_list in H_count.items():
    for w, h_list in W_count.items():
        count = len(w_list) + len(h_list)
        if w in w_list or h in h_list:
            count -= 1
        max_count = max(max_count, count)

print(max_count)

### FIXED CODE ###

H, W, M = map(int, input().split())

cnt_h = [0] * (H + 1)
cnt_w = [0] * (W + 1)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    cnt_h[h] += 1
    cnt_w[w] += 1
    points.add((h, w))

H_max = max(cnt_h)
W_max = max(cnt_w)

H_max_num = [i for i, cnt in enumerate(cnt_h) if cnt == H_max]
W_max_num = [i for i, cnt in enumerate(cnt_w) if cnt == W_max]

flag = 0
for h_num in H_max_num:
    for w_num in W_max_num:
        if (h_num, w_num) not in points:
            print(H_max + W_max)
            exit()

print(H_max + W_max -1)
### BUGGY CODE ###

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

# dp[i] := 足場iに来るのにかかる最小のコスト
INF = 10**18
dp = [INF for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    c = INF
    for j in range(1, K + 1):
        idx = i - j
        if idx < 0:
            continue
        v = dp[idx] + abs(H[i] - H[idx])
        c = min(v, c)
    dp[i] = c
# print('dp', dp)
ans = dp[-1]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [H[0]] * K + H

# dp[i] := 足場iに来るのにかかる最小のコスト
INF = 10**18
dp = [INF] * (K + N)
dp[0] = 0
for i in range(K, N + K):
    h = H[i]
    dp[i] = min(x + abs(y - h) for x, y in zip(dp[i - K:i], H[i - K:i]))
#     for j in range(1, K + 1):
#         v = dp[i - j] + abs(H[i] - H[i - j])
#         dp[i] = min(dp[i], v)
# print('dp', dp)
ans = dp[-1]
print(ans)
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
lst.sort()
bridge = [True] * N

def connected(a, b):
    for i in range(a, b):
        if bridge[i] == False:
            return False
    return True

def solve():
    res = 0
    for l in lst:
        a, b = reversed(l)
        if connected(a, b):
            bridge[b - 1] = False
            res += 1
    return res

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

bridge = set()
def connected(a, b):
    for i in bridge:
        if a <= i and i < b:
            return False
    return True
def solve():
    N, M = [int(x) for x in input().split()]
    lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
    lst.sort()
    res = 0
    for l in lst:
        a, b = l
        if connected(b, a):
            bridge.add(a - 1)
    return len(bridge)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

import math
from itertools import permutations
d,g = map(int,input().split())
x = []
for i in range(d):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
zy = [i for i in range(1,d+1)]
zyu = list(permutations(zy, d))
ans2 = 100000000000000000000000
gou = g+0
for i in zyu:
  ans = 0
  g = gou +0
  while g > 0:
    for j in i:
      if g <= 0:
        break
      dai = x[-j][0]
      if g > (d-j+1)*100*dai:
        g-= ((d-j+1)*100*dai +x[-j][1])
        ans += dai
        continue
      else:
        ans += math.ceil(g/((d-j+1)*100))
        g = 0
      g -= x[-j][1]
  ans2 = min(ans,ans2)
print(int(ans2))

### FIXED CODE ###

import math
from itertools import combinations
d,g = map(int,input().split())
x = []
for i in range(d):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
zy = [i for i in range(1,d+1)]
zyu = []
for i in range(d+1):
  zyu.extend(list(combinations(zy, i)))
ans2 = 100000000000000000000000
gou = g+0
for i in zyu:
  ans = 0
  g = gou +0
  for j in i:
    g -= (x[j-1][0] * j*100 + x[j-1][1])
    ans += x[j-1][0]
  if g >0:
    y = d+0
    while y in i:
      y -= 1
    a = x[y-1][0]
    if g > a*y*100:
      continue
    ans += math.ceil(g/(y*100))
  ans2 = min(ans,ans2)
print(ans2)