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

n = int(input())
s = input()
RL = []
GL = []
BL = []
for i in range(1, n + 1):
    word = s[i - 1]
    if word == "R":
        RL.append(i)
    elif word == "G":
        GL.append(i)
    else:
        BL.append(i)
ans = 0
for r in RL:
    for g in GL:
        for b in BL:
            if 3 * (max(r, g, b) + min(r, g, b)) == 2 * (r + g + b):
                continue
            ans += 1
print(ans)


### FIXED CODE ###

# from bisect import bisect_left

n = int(input())
s = input()
RL = []
GL = []
BL = []
for i in range(1, n + 1):
    word = s[i - 1]
    if word == "R":
        RL.append(i)
    elif word == "G":
        GL.append(i)
    else:
        BL.append(i)
nagasa_r = len(RL)
nagasa_g = len(GL)
nagasa_b = len(BL)
SBL = set(BL)
ans = 0
if nagasa_b == 0 or nagasa_g == 0 or nagasa_r == 0:
    ans = 0
else:
    out_count = 0
    for r in RL:
        for g in GL:
            bigger = max(r, g)
            smaller = min(r, g)
            delta = bigger - smaller
            if (r + g) % 2 == 0:
                outnumber = [bigger + delta, smaller - delta, (r + g) // 2]
            else:
                outnumber = [bigger + delta, smaller - delta]
            for num in outnumber:
                if num in SBL:
                    out_count += 1
            ans += nagasa_b
    ans -= out_count
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
for _ in range(n):
    w, v = map(int, input().split())
    for wk in range(cap,w-1,-1):
        val[wk]=max(val[wk],val[wk-w]+v)
print(val[-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))
### BUGGY CODE ###

from collections import deque

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #queの定義
    que = deque([])
   
    for i in range(n):
        for j in range(m):
            # スタートとゴールの座標を探す
            if maze[i][j] == "#":
                sx = i
                sy = j
                que.append((sx, sy))
                d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    ans = 0
    for i in range(n):
        for j in range(m):
            ans = max(ans, d[i][j])
    
    return ans

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]

print(bfs())


### FIXED CODE ###

from collections import deque

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #queの定義
    que = deque([])
   
    for i in range(n):
        for j in range(m):
            # スタートとゴールの座標を探す
            if maze[i][j] == "#":
                sx = i
                sy = j
                que.append((sx, sy))
                d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    ans = 0
    for i in range(n):
        for j in range(m):
            ans = max(ans, d[i][j])
    
    return ans

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]

print(bfs())
### BUGGY CODE ###

A, B, K = map(int, input().split())
l = []
for i in range(A, B+1):
    l.append(i)
    
if B - (A-1) <= 2*K:
    for j1 in l:
        print(j1)
else:
    m = l[:K] + l[-K:]
    for j in m:
        print(j)

### FIXED CODE ###

A, B, K = map(int, input().split())
    
if B - (A-1) < 2*K:
    l = []
    for i in range(A, B+1):
        l.append(i)
    for j1 in l:
        print(j1)
else:
    for j2 in range(A, A+K):
        print(j2)
    for j3 in range(B-K+1, B+1):
        print(j3)
### BUGGY CODE ###

import numpy as np

#n, d = map(int, input().split())
n= int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

for i in range(n):
    ii = a[i]
    a[i]= 0
    m = max(a)
    a[i] = ii
    print(m)




### FIXED CODE ###

import numpy as np
n= int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
    
b = np.array(a)
b = np.sort(b)[::-1]

ans = [0]*n

for i in range(n):
    if a[i] == b[0]:
        ans[i] = b[1]
    else:
        ans[i] = b[0]
        
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

n,m=map(int,input().split())
a = list(map(int,input().split()))
for i in range(1,m+1):
  l = a.index(max(a))
  a[l] = a[l] // 2
print(sum(a))



### FIXED CODE ###

import heapq
import math
n,m=map(int,input().split())
a = list(map(int,input().split()))
h = []
for _a in a:
  heapq.heappush(h,-_a)
for i in range(m):
  heapq.heappush(h,math.ceil(heapq.heappop(h) / 2))
print(sum(h)*(-1))
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
idx = N // 2
lb = 0

while True:
  if idx == N-1: # すべて左に出た
    lb = N-1
    break
  l = sim(idx)
  r = sim(idx+1)
  if l == -1 and r != -1: # 境界がみつかった
    lb = idx
    break
  if l == -1:
    idx = (idx + N) // 2
  else:
    idx = idx // 2

# 右側の境界を探索
idx = N // 2
rb = 0

while True:
  if idx == 0: # すべて右に出た
    rb = 0
    break
  l = sim(idx)
  r = sim(idx+1)
  if l != N and r == N: # 境界が見つかった
    rb = idx
    break
  if l != N:
    idx = (idx + N) // 2 
  else:
    idx = idx // 2

print(rb - lb)


### FIXED CODE ###

# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)
### BUGGY CODE ###

import sys
from collections import Counter

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    res = tuple(sorted((i, inp[0])))
    if ct.get(res) is None:
        ct[res] = 1
    else:
        ct[res] += 1
    a_ls[i] = inp[1:]
cnt = 0
while sum(ct.values()) > 0:
    ls = []
    flg = False
    for k, v in ct.items():
        if v > 1:
            if len(a_ls[k[0]]) > 0:
                ls.append(tuple(sorted((a_ls[k[0]][0], k[0]))))
                a_ls[k[0]].pop(0)
            if len(a_ls[k[1]]) > 0:
                ls.append(tuple(sorted((a_ls[k[1]][0], k[1]))))
                a_ls[k[1]].pop(0)
            ct[k] = 0
            flg = True
    for l in ls:
        if ct[l] is None:
            ct[l] = 0
        ct[l] += 1
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())
def gcd(x, y):
    xx = (abs(x+y)-abs(x-y)) // 2
    yy = (abs(x+y)+abs(x-y)) // 2
    if yy % xx == 0:
        return xx
    else:
        return gcd(yy % xx, xx)
 
g = gcd(C, D)
Cmax = 0
Hmax = 0
Smax = 0
for p in range(F // (100*A) + 2):
    for q in range((F - 100*p*A) // (100*B) + 2):
        H2O = 100 * p * A + 100 * q * B
        lev = min([F - H2O, E*H2O // 100])
        sugar = 0
        if lev > 0 and H2O != 0:
            if lev < C:
                sugar = 0
            elif lev < C + D - q:
                sugar = max([(lev // C)*C, (lev//D)*D,])
            else:
                sugar = (lev // g) * g
            if Cmax*(H2O+sugar) <= sugar:
                Cmax = sugar / (H2O+sugar)
                Hmax = H2O
                Smax = sugar
import time
time.sleep(A*0.5)
print("{0} {1}".format(Smax+Hmax, Smax))


### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())
def gcd(x, y):
    xx = (abs(x+y)-abs(x-y)) // 2
    yy = (abs(x+y)+abs(x-y)) // 2
    if yy % xx == 0:
        return xx
    else:
        return gcd(yy % xx, xx)

g = gcd(C, D)
Cmax = 0
Hmax = 0
Smax = 0
for p in range(F // (100*A) + 2):
    for q in range((F - 100*p*A) // (100*B) + 2):
        H2O = 100 * p * A + 100 * q * B
        lev = min([F - H2O, E*H2O // 100])
        sugar = 0
        if lev > 0 and H2O != 0:
            if lev < C:
                sugar = 0
            elif lev < C + D - q:
                sugar = max([(lev // C)*C, (lev//D)*D,])
            else:
                sugar = (lev // g) * g
            if Cmax*(H2O+sugar) <= sugar:
                Cmax = sugar / (H2O+sugar)
                Hmax = H2O
                Smax = sugar

print("{0} {1}".format(Smax+Hmax, Smax))
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if (j - i != k - j) & (i < j < k):
                if (s[i] != s[j]) & (s[j] != s[k]) & (s[k] != s[i]):
                    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = list(input())
cnt = 0

cnt = s.count("R") * s.count("B") * s.count("G")
# j - i = k -j を求める。
sub = 0 
for i in range(n):
    for j in range(i, n):
        k = 2 * j - i
        if k <= n - 1:
            if (s[i] != s[j]) and (s[j] != s[k]) and (s[i] != s[k]):
                sub += 1

print(cnt-sub)
### BUGGY CODE ###

n=int(input())

s=[]
cnt=0

for i in range(n):
  a=str(input())
  if a in s:
    continue

  else:
    s.append(a)
    cnt+=1

print(cnt)

### FIXED CODE ###

n=int(input())

s={}
cnt=0

for i in range(n):
  a=str(input())
  if a in s:
    continue

  else:
    s[a]=1
    cnt+=1

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

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

setA = set(A)
counts = {}
for e in setA:
    counts[e] = A.count(e)

ans = 0
for e in setA:
    ans += counts[e] * (counts[e]-1) // 2

for i in range(0, len(A)):
    e = A[i]
    print(ans - (counts[e] * (counts[e]-1) // 2) +
          ((counts[e]-1) * (counts[e]-2) // 2))


### FIXED CODE ###

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

counts = {}
for e in A:
    if e not in counts:
        counts[e] = 0
    counts[e] += 1

ans = 0
for e in counts:
    ans += counts[e] * (counts[e]-1) // 2

for i in range(0, len(A)):
    print(ans - counts[A[i]] + 1)
### BUGGY CODE ###

N = int(input())

xy = [0] + [tuple(map(int, input().split())) for _ in range(N)]
m = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        xyi = xy[i]
        xyj = xy[j]
        tmp = abs(xyi[0]-xyj[0]) + abs(xyi[1]-xyj[1])
        if m < tmp:
            m = tmp
print(m)

### FIXED CODE ###

n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]

w = [xy[i][0] - xy[i][1] for i in range(n)]
z = [xy[i][0] + xy[i][1] for i in range(n)]
print(max((max(w) - min(w)), (max(z)-min(z))))
### BUGGY CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
d = {}
d_self ={}
sets = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

for i in m:
    if i in sets:
        print(sets[i])
    else:
        cnt = 0
        for j,k in c.items():
            if j == i:
                if k - 1 >= 2:
                    d_self.setdefault(j, ans(k-1))
                    cnt += d_self[j]
                
            else:
                d.setdefault(j, ans(k))
                cnt += d[j]
        sets[i] = cnt
        print(cnt)

### FIXED CODE ###

import collections
import math

n = int(input())

m = list(map(str,input().split()))

c = dict(collections.Counter(m))
d = {}
hyouji = {}
def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

cnt = 0
for i,j in c.items():
    n = ans(j)
    d[i] = n
    cnt += n


for k in m:
    if k in hyouji:
        print(hyouji[k])
    else: 
        if c[k] < 2:
            q = cnt
        elif c[k] == 2:
            q = cnt - 1
        else:
                q = cnt -d[k] + ans(c[k] - 1)

        hyouji[k] = q
        print(hyouji[k])
### BUGGY CODE ###

from collections import defaultdict as dd
n,w=map(int,input().split())
we=[0]*n
val=[0]*n
for i in range(n):
  ww,v=map(int,input().split())
  we[i]=ww
  val[i]=v
dp=dd(lambda:-1)
def solve(i,w,we,val):
  if(i==0 or w==0):
    return 0
  if(dp[(i,w)]!=-1):
    return dp[(i,w)]
  if(we[i-1]<=w):
    dp[(i,w)]=max(val[i-1]+solve(i-1,w-we[i-1],we,val),solve(i-1,w,we,val))
    return dp[(i,w)]
  else:
    dp[(i,w)]=solve(i-1,w,we,val)
    return dp[(i,w)]
print(solve(n,w,we,val))
#print(dp)  


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
maxn=10000000000000000
we=[0]*n
val=[0]*n
su=0
for i in range(n):
    ww,v=map(int,input().split())
    we[i]=ww
    val[i]=v
    su+=v
dp=[maxn]*(su+1)
dp[0]=0
for i in range(n):
    for j in range(su-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],we[i]+dp[j])
ans=0
for i in range(len(dp)):
    if(dp[i]<=w):
        ans=max(ans,i)
print(ans)
### BUGGY CODE ###

import numpy as np

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

ans = [0 for _ in range(n)]
for i in range(n):
  tmpidx = np.argmin(A)
  A[tmpidx] = np.inf
  ans[i] = tmpidx+1

print(*ans)

### FIXED CODE ###

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

ans = [0 for _ in range(n)]
for i in range(n):
  ans[A[i]-1] = i+1

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

N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[N]%(10**9+7))


### FIXED CODE ###

N,M = map(int,input().split())
A = set(int(input()) for _ in range(M))
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[N]%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
    if flag:
        continue
    else:
        bridge[q-1]=1
print(sum(bridge))

### FIXED CODE ###

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

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

order = int(input())
data = []
ans = 0

for i in range(order):
    val = input()
    if val not in data:
        data.append(val)
        ans += 1

print(ans)

### FIXED CODE ###

order = int(input())
data = set([])

for i in range(order):
    data.add(input())

print(len(data))
### BUGGY CODE ###

s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    for i in range(len(s)):
        if s[i] == a:
            q = 1
            while i + q <= len(s):
                if s[i:i + q] not in num:
                    num.append(s[i:i + q])
                q += 1

num = sorted(num)
print(num[k - 1])

### FIXED CODE ###

s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    indexes = [i for i, x in enumerate(s) if x == a]
    z = 0
    while z < len(indexes):
        i = indexes[z]
        q = 1
        while q <= 5:
            if s[i:i + q] not in num:
                num.append(s[i:i + q])
            q += 1
        z += 1

num = sorted(num)
print(num[k - 1])
### BUGGY CODE ###

from itertools import permutations
N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
T = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = tuple(map(int, input().split()))
    T[a-1][b-1] = c
    T[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            T[i][j] = min(T[i][j],T[i][k]+T[k][j])

print(min(sum(T[r1-1][r2-1] for r1, r2 in zip(rs, rs[1:])) for rs in permutations(R)))

### FIXED CODE ###

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

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    ans = INF
    for rs in permutations(R):
        cost = 0
        for i in range(RR-1):
            cost += T[rs[i]-1][rs[i+1]-1]
        ans = min(ans, cost)
    print(ans)

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


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

h.sort()
h.reverse()

en = []
ans = 0

for i, j in enumerate(h):
    # en.append(j)
    # print([h[0],h[0]])
    if i == 0:
        en.append((h[0],h[0]))
    else:
        mintmp = min(en[0])
        maxtmp = max(en[0])
        ans += mintmp
        en.append((maxtmp, h[i]))
        en.append((mintmp, h[i]))
        en.pop(0)

    # print(en)

print(ans)

### FIXED CODE ###

from collections import deque

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

h.sort()
h.reverse()

en = deque()
ans = 0

for i, j in enumerate(h):
    if i == 0:
        en.append((j,j))
    else:
        maxtmp, mintmp = en.popleft()
        ans += mintmp
        en.append((maxtmp, j))
        en.append((mintmp, j))

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

n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)


### FIXED CODE ###

n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)
### BUGGY CODE ###

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
b=[]
for i in a:
	ma=i[0] + i[1]
	mi=i[0] - i[1]
	c=[mi,ma]
	b.append(c)


while True:
	count=[]
	for i in range(n):
		count.append(0)
	p=0
	for i in b:
		p+=1
		for j in b:
			if i==j:
				continue
			if i[0]<j[0]<i[1] or i[0]<j[1]<i[1]:
				count[p-1]+=1
	del b[count.index(max(count))]
	n-=1
	if sum(count)==0:
		break

print(len(count))

### FIXED CODE ###

N=int(input())
xl=[]
for i in range(N):
  x,l=map(int,input().split())
  xl.append([x-l,x+l])

XL=sorted(xl,key=lambda x:x[1])

w=1
robot=XL[0]
for i in XL:
  if robot[1] <= i[0]:
    w+=1
    robot=i
print(w)
### BUGGY CODE ###

def kk(n,m):
    if n<m:
        n,m=m,n
    while  n%m!=0:
        n=n%m
        n,m=m,n
    return m


k= int(input())
count=0
for p in range(1,k+1):
    for q in range(1,k+1):
        pq=  kk(p,q)
        for r in range(1,k+1):
             pqr= kk(pq,r)
             count= count+ pqr
print(count)

### FIXED CODE ###

def kk(n,m):
    if n<m:
        n,m=m,n
    while  n%m!=0:
        n=n%m
        n,m=m,n
    return m


k= int(input())
count=0
for p in range(1,k+1):
    for q in range(p,k+1):
        pq=  kk(p,q)
        for r in range(q,k+1):
            pqr= kk(pq,r)
            if p==r:
                 pqr=pqr
            elif p==q or q==r:
                pqr=pqr*3
            else:
                pqr=pqr*6
            count= count+ pqr
print(count)
### BUGGY CODE ###

N, W = map(int, input().split())
INF = -10 ** 12

# 重さW以下の時の価値の最大値
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j - w >= 0:
            dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][W])

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
INF = -10 ** 12

# 重さW以下の時の価値の最大値
dp = np.zeros((N, W + 1), dtype=np.int64)

for i in range(0, N):
    w, v = map(int, input().split())
    dp[i][:w] = dp[i-1][:w]
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)

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

H, N = map(int,input().split())
data = []

for i in range(N):
    data.append([0, 0])
    a, b = map(int,input().split())
    data[i][0] = a
    data[i][1] = b
data.sort(key=lambda x: x[0])
cost = [float("inf")] * (H + data[-1][0])
cost[0] = 0
for i in range(1, H + data[-1][0]):
    for magic in data:
        if i < magic[0]:
            break
        if cost[i] > cost[i - magic[0]] + magic[1]:
            cost[i] = cost[i - magic[0]] + magic[1]
print(min(cost[H:]))

### FIXED CODE ###

H, N = map(int,input().split())
data = []

for i in range(N):
    data.append([0, 0])
    a, b = map(int,input().split())
    data[i][0] = a
    data[i][1] = b
data.sort(key=lambda x: x[0])
cost = [float("inf")] * (H + data[-1][0])
cost[0] = 0
for i in range(1, H + data[-1][0]):
    for magic in data:
        if i < magic[0]:
            break
        if cost[i] > cost[i - magic[0]] + magic[1]:
            cost[i] = cost[i - magic[0]] + magic[1]
print(min(cost[H:]))