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

d, g = map(int, input().split())

p = []
c = []

for i in range(d):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)

minp = sum(p)

def min_plobrem(p,c):
    res = []
    if len(p) == 1:
        for i in range(p[0]+1):
            point = 100 * i
            if i == p[0]:
                point += c[0]
            res.append([point,i])
    else:
        for lelse in min_plobrem(p[:-1],c[:-1]):
            for i in range(p[-1]+1):
                point = 100 * len(p) * i
                if i == p[-1]:
                    point += c[-1]
                res.append([lelse[0]+point, lelse[1]+i])
    return(res)

results = min_plobrem(p,c)
for result in results:
    if result[0] >= g:
        minp = min(minp, result[1])

print(minp)

### FIXED CODE ###

d, g = map(int, input().split())

p = []
c = []

for i in range(d):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)

def two_list(d):
    if d == 1:
        return [[0],[1]]
    else:
        res = []
        prevlist = two_list(d-1)
        for l in prevlist:
            tmp = l + [0]
            res.append(tmp)
            tmp = l + [1]
            res.append(tmp)
        return res

s = []
for i in range(d):
    sump = 100 * (i+1) * p[i] + c[i]
    s.append(sump)

minp = sum(p)

for twolist in two_list(d):
    sumall = 0
    sumnum = 0
    for i in range(d):
        sumall += s[i] * twolist[i]
        sumnum += p[i] * twolist[i]
    if 0 in twolist:
        max0 = d - twolist[::-1].index(0)
    else:
        break
    if sumall >= g:
        minp = min(minp, sumnum)
    elif sumall < g and (g-sumall) < s[max0-1]:
        add = (g-sumall)//(100*max0)
        sumnum += add
        if (g-sumall)%(100*max0) != 0:
            sumnum += 1
        minp = min(minp, sumnum)

print(minp)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())

    min_num = N
    while True:
        dif = abs(min_num - K)
        if dif < min_num:
            min_num = dif
        else:
            break
    print(min_num)
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())

    remainder = N % K
    if abs(remainder - K) < remainder:
        ans = abs(remainder - K)
    else:
        ans = remainder
    print(ans)


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

def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    num = (10 ** 9) + 7
    for i in range(n):
        for j in range(i+1, n):
            ans += (a[i] * a[j]) % num
    
    ans = int(ans % num)
    print(int(ans % num))

resolve()

### FIXED CODE ###

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

    ans = 0
    mod = (10 ** 9) + 7
    csum = sum(a)

    for i in range(n):
        csum -= a[i]
        ans += a[i] * csum

    ans = int(ans % mod)
    print(ans)
 
resolve()
### BUGGY CODE ###

S = input().split()
N = int(S[0])
M = int(S[1])
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_MAX = max(A)
B_MAX = max(B)
MAX = A_MAX if (A_MAX > B_MAX) else B_MAX

mod = int(1e9 + 7)

A_F_cnt = 0
B_F_cnt = 0

result = 1
sA = [ False for _ in range(MAX+1) ]
sB = [ False for _ in range(MAX+1) ]

for i in range(len(A)):
    sA[A[i]] = True
for i in range(len(B)):
    sB[B[i]] = True


for i in range(MAX, 0, -1):
    in_A = sA[i]
    in_B = sB[i]
    if (in_A and in_B):
        A_F_cnt += 1
        B_F_cnt += 1
    elif (in_A):
        result *= B_F_cnt
        A_F_cnt += 1 
    elif (in_B):
        result *= A_F_cnt
        B_F_cnt += 1
    else:
        coef = ( ( A_F_cnt * B_F_cnt )%mod - (N*M - i) )
        if coef < 0:
            coef += mod
        result *= coef
        
    # print(in_A, in_B, A_F_cnt, B_F_cnt, result)

print(result % mod)



### FIXED CODE ###

S = input().split()
N = int(S[0])
M = int(S[1])
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_MAX = max(A)
B_MAX = max(B)
MAX = A_MAX if (A_MAX > B_MAX) else B_MAX

mod = int(1e9 + 7)

A_F_cnt = 0
B_F_cnt = 0

result = 1
sA = [ False for _ in range(MAX+1) ]
sB = [ False for _ in range(MAX+1) ]

for i in range(len(A)):
    sA[A[i]] = True
for i in range(len(B)):
    sB[B[i]] = True


for i in range(MAX, 0, -1):
    in_A = sA[i]
    in_B = sB[i]
    if (in_A and in_B):
        A_F_cnt += 1
        B_F_cnt += 1
    elif (in_A):
        result *= B_F_cnt
        result %= mod
        A_F_cnt += 1 
    elif (in_B):
        result *= A_F_cnt
        result %= mod
        B_F_cnt += 1
    else:
        coef = ( ( A_F_cnt * B_F_cnt )%mod - (N*M - i) )
        if coef < 0:
            coef += mod
        result *= coef
        result %= mod
        
    # print(in_A, in_B, A_F_cnt, B_F_cnt, result)

print(result % mod)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import log2

ROUND = 10 ** 100
LOG = int(log2(ROUND))

def main():
    S = input()
    N = len(S)
    to = []
    for _ in range(LOG):
        l = [0] * N
        to.append(l)
    
    for i in range(N):
        to[0][i] = i + 1 if S[i] == "R" else i - 1
    
    for i in range(1, LOG):
        for j in range(N):
            to[i][j] = to[i - 1][to[i - 1][j]]

    a = []
    for i in range(LOG):
        if ROUND>>i & 1:
            a.append(i)

    ans = [0] * N
    for j in range(N):
        ans[to[LOG - 1][j]] += 1

    L = [str(i) for i in ans]
    print(" ".join(L))
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import groupby

# RUN LENGTH ENCODING
def rfe_tupple(S: str):
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, str(len(list(v)))))
    return res

def main():
    S = input()
    N = len(S)
    
    now = 0
    compressed = rfe_tupple(S)
    ans = [0] * N
    for lr, i in compressed:
        i = int(i)
        if lr == "R":
            now += i
            ans[now - 1] += i - i // 2
            ans[now] += i // 2
        else:
            ans[now - 1] += i // 2
            ans[now] += i - i // 2
            now += i
    
    L = [str(i) for i in ans]
    print(" ".join(L))
    return

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

from collections import deque
n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


print(ans)


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


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

import sys
import math

n,h = map(int,input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n) :
  a[i],b[i] = map(int,input().split())
  
b.sort(reverse=True)

c = 0
for i in range(n) :
  if b[i] < max(a) :
    break
  h -= b[i]
  c += 1
  if h <= 0 :
    print(c)
    sys.exit()

print(c + math.ceil(h/max(a)))

### FIXED CODE ###

import sys
import math
import bisect

n,h = map(int,input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n) :
  a[i],b[i] = map(int,input().split())
  
b.sort(reverse=True)

c = 0
bs = [b[0]]
am = max(a)
bs_append = bs.append
for i in range(1,n) :
  if b[i] < am :
    break
  bs_append(bs[i-1]+b[i])
  
if b[0] < am :
  print(math.ceil(h/am))
  sys.exit()

if bs[-1] <= h :
  print(len(bs) + math.ceil((h-bs[-1])/am))
else :
  print(bisect.bisect_left(bs,h)+1)
### BUGGY CODE ###

import math

n = list(map(int,input().split()))
hikaku = 0

for x in range(1,n[2]+1):
    m = math.floor(n[0] * x / n[1]) - n[0] * math.floor(x / n[1])
    if hikaku < m:
        hikaku = m

print(hikaku)

### FIXED CODE ###

import math

n = list(map(int,input().split()))
x = min(n[1]-1 , n[2])
if n[2] >= n[2]:
    print(math.floor(n[0] * x / n[1]))
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
lis = []
for _ in range(a):
  lis.append(1)
for _ in range(b):
  lis.append(0)
for _ in range(c):
  lis.append(-1)
sum = 0
for _ in range(k):
  sum += max(lis)
  lis.remove(max(lis))
print(sum)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
if k <= a:
    print(k)
elif k <= a + b:
    print(a)
else:
    print(a -1*(k - a - b))
### BUGGY CODE ###

k,s=map(int,input().split())

ans=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                ans+=1
print(ans)


### FIXED CODE ###

k,s = map(int, input().split())
print(len([s-y-z for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

N = int(input())
X = input()

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

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

passable = [1]*(N+1)

for l,r in LR:
    for i in range(l):
        passable[i]=0
    for i in range(r+1, N+1):
        passable[i]=0

print(passable.count(1))

### FIXED CODE ###

N,M = map(int, input().split())
L = [0]*M
R = [0]*M

for i in range(M):
    L[i],R[i] = map(int, input().split())
    
l = max(L)
r = min(R)

print(max(r-l+1,0))
### BUGGY CODE ###

from heapq import heappush, heappop
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(L, -q[1])
            heappush(R, -heappop(L))
        else:
            heappush(R, q[1])
            heappush(R, q[1])
            heappush(L, -heappop(R))
    else:
        print(-L[0], B+M)

### FIXED CODE ###

from heapq import heappush, heappop
def inpl(): return list(map(int, input().split()))

Q = int(input())
L = []
R = []

B = 0
M = 0

for _ in range(Q):
    q = inpl()
    if len(q) == 3:
        B += q[2]
        if len(R) == 0:
            L.append(-q[1])
            R.append(q[1])
            continue

        M += min(abs(-L[0] - q[1]), abs(R[0] - q[1])) * (not (-L[0] <= q[1] <= R[0]))
        if q[1] < R[0]:
            heappush(L, -q[1])
            heappush(L, -q[1])
            heappush(R, -heappop(L))
        else:
            heappush(R, q[1])
            heappush(R, q[1])
            heappush(L, -heappop(R))
    else:
        print(-L[0], B+M)
### BUGGY CODE ###

N = int(input())
input_line = [input() for _ in range(N)]
count = {}
for x in list(set(input_line)):
    count[x] = input_line.count(x)
max_count = max(count.values())
result = sorted([k for k, v in count.items() if v == max_count])
for x in result:
    print(x)

### FIXED CODE ###

N = int(input())
input_line = [input() for _ in range(N)]
count = {}
for w in input_line:
    if w in count:
        count[w] += 1
    else:
        count[w] = 1
max_values = max(count.values())
keys = [k for k, v in count.items() if v == max_values]
for w in sorted(keys):
    print(w)
### BUGGY CODE ###

N, M = map(int, input().split())

INF = 10**9 + 7

def frac(n):
    ans = n
    while n>1:
        ans *= (n-1)
        n -= 1
    return ans
    # if n<= 1:
    #     return 1
    # return n*frac(n-1)
    
if abs(N-M) > 1:
    print(0)
elif abs(N-M) == 1:
    print(frac(N)*frac(M)%INF)
else:
    print(((frac(N)*frac(M))*2)%INF)


### FIXED CODE ###

from math import factorial as frac

N, M = map(int, input().split())

INF = 10**9 + 7

if abs(N-M) > 1:
    print(0)
elif abs(N-M) == 1:
    print(frac(N)*frac(M)%INF)
else:
    print(((frac(N)*frac(M))*2)%INF)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
line=[A[0]]
for i in range(1,N):
    ans+=line.pop(0)
    line.append(A[i])
    line.append(A[i])
print(ans)

### FIXED CODE ###

import heapq
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
line=[]
heapq.heappush(line,-A[0])
for i in range(1,N):
    ans-=heapq.heappop(line)
    heapq.heappush(line,-A[i])
    heapq.heappush(line,-A[i])
print(ans)
### BUGGY CODE ###

A, B, M = map(int, input().split())
Ma = [int(_) for _ in input().split()]
Mb = [int(_) for _ in input().split()]
Mm = [[int(_) for _ in input().split()] for __ in range(M)]

r = 10 ** 5
for i in range(A):
  for j in range(B):
    c = max([z for x,y,z in Mm if x == i+1 and y == j+1], default=0)
    r = min(r, Ma[i] + Mb[j] - c)
print(r)

### FIXED CODE ###

# AtCoder Hitachi B
A, B, M = map(int, input().split())
Ma = [int(_) for _ in input().split()]
Mb = [int(_) for _ in input().split()]
Mm = [[int(_) for _ in input().split()] for __ in range(M)]
# unuse vaucher
r0 = min(Ma) + min(Mb)
# use vaucher
r1 = min([Ma[x-1]+Mb[y-1]-c for x,y,c in Mm])
print(min(r0,r1))
### BUGGY CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
#for i in range(1,max(a)+1):
#for i in range(1,10**5+1):
#    if not i in adic:
#        adic[i]=0
        
        
q=int(input())
b=[0]*(q+1)
c=[0]*(q+1)
for i in range(q):
    bi,ci=map(int,input().split())
    b[i]=bi
    c[i]=ci
    
#print(adic)    
for i in range(q):
    if b[i] in adic and c[i] in adic:
        adic[c[i]]=adic[c[i]]+adic[b[i]]
        adic[b[i]]=0
    elif b[i] in adic and (not c[i] in adic):
        adic[c[i]]=adic[b[i]]
        adic[b[i]]=0
#    print(i,adic)
    asum=0
    for i,ad in adic.items():
        asum+=i*ad
    print(asum)
    

### FIXED CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
q=int(input())
b=[0]*(q)
c=[0]*(q)
bc=[[0]*2 for i in range(q)]
for i in range(q):
    bc[i]=map(int,input().split())
    
asum=0
for i,ad in adic.items():
    asum+=i*ad
    
#print(adic)    
for bi,ci in bc:
    if bi in adic and ci in adic:
        asum-=bi*adic[bi]
        adic[ci]=adic[ci]+adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
    elif bi in adic and (not ci in adic):
        asum-=bi*adic[bi]
        adic[ci]=adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
#    print(i,adic)
    print(asum)
### BUGGY CODE ###

n = int(input())
i = 1
divisor = n
min_value = 10 ** 10 + 1
while i <= divisor:
    if n % i == 0:
        divisor = n // i
        if max(len(str(i)),len(str(n // i))) > min_value:
            break
        min_value = min(min_value,max(len(str(i)),len(str(n // i))))
    i += 1
print(min_value)


### FIXED CODE ###

n = int(input())
i = 1
divisor = n ** 0.5
min_value = 10 ** 10 + 1
while i < divisor + 1:
    if n % i == 0:
        min_value = min(min_value,max(len(str(i)),len(str(n // i))))
    i += 1
print(min_value)
### BUGGY CODE ###

import sys
N = input()
A = list(map(int,input().split()))
total = 1
for a in A:
    total *= a
if total>10**18:
    print(-1)
    sys.exit()
print(total)

### FIXED CODE ###

import sys
N = input()
A = list(map(int,input().split()))
B = False
total = 1
for a in A:
    if a == 0:
        print(0)
        sys.exit()
    elif total <=10**18:
        total *= a
    else:
        B = True
if B or total>10**18:
    print(-1)
else:
    print(total)
### BUGGY CODE ###

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

dp = [-1] * n
dp[0] = 0

for i in range(1, min(n, k)):
    dp[i] = min([dp[j] + abs(h[i]-h[j]) for j in range(i)])

for i in range(k, n):
    dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(1, k+1)])

print(dp[n-1])

### FIXED CODE ###

import sys

data = sys.stdin.readlines()

n, k = list(map(int, data[0].split()))
h = list(map(int, data[1].split()))

dp = [-1] * n
dp[0] = 0

for i in range(1, min(n, k)):
    dp[i] = min([dp[j] + abs(h[i]-h[j]) for j in range(i)])

for i in range(k, n):
    dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(1, k+1)])

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

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

passcard = []
for c in range(l[0][1] - l[0][0]+1):
    passcard.append(l[0][0]+c)

#print(passcard)

for t in range(n[1]):
    for i in range(len(passcard)):
        if not(l[t][0] <= passcard[i] <= l[t][1]):
            passcard[i] = 0
            #print(passcard)
        else:
            passcard[i] = passcard[i]
            
out = [i for i in passcard if i!=0]
#print(out)
print(len(out))

### FIXED CODE ###

n = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(n[1])]
minp = l[0][0]
maxp = l[0][1]
for t in range(n[1]):
    minp = max(minp,l[t][0])
    maxp = min(maxp,l[t][1])
print(max(0,maxp-minp+1))
### BUGGY CODE ###

def rec(n, w, ws, vs, dp):
    if w == 0 or n < 0:
        return 0
    if ws[n] <= w:
        dp[n][w] = max(dp[n][w], rec(n-1, w-ws[n], ws, vs, dp) + vs[n])
    dp[n][w] = max(dp[n][w], rec(n-1, w, ws, vs, dp))
    return dp[n][w]

def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[-1] * (w + 1) for _ in range(n + 1)]
    print(rec(n-1, w, ws, vs, dp))
resolve()

### FIXED CODE ###

def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            if j >= ws[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j - ws[i]] + vs[i])
            dp[i][j] = max(dp[i][j], dp[i-1][j] if i - 1 >= 0 else 0)
    print(dp[n-1][w])
resolve()
### BUGGY CODE ###

n=int(input())
s=list(input())
ans=0
how_r=[0 for i in range(n+1)]
how_g=[0 for i in range(n+1)]
how_b=[0 for i in range(n+1)]
for i in range(n):
    string=s[i]
    if string=="R":
        how_r[i+1]+=1
    elif string=="G":
        how_g[i+1]+=1
    elif string=="B":
        how_b[i+1]+=1
for i in range(n):
    how_r[i+1]+=how_r[i]
    how_g[i+1]+=how_g[i]
    how_b[i+1]+=how_b[i]


for  i in range(n):
    for j in range(i+1,n):
        x=s[i]
        y=s[j]
        if x!=y:
            if "R" not in [x,y]:
                ans+=how_r[j+1]-how_r[i]
                if (i+j)%2==0:
                    if s[(i+j)//2]=="R":
                        ans-=1
                
            
            elif "G" not in [x,y]:
                ans+=how_g[j+1]-how_g[i]
                if (i+j)%2==0:
                    if s[(i+j)//2]=="G":
                        ans-=1
                
            elif "B" not in [x,y]:
                ans+=how_b[j+1]-how_b[i]
                if (i+j)%2==0:
                    if s[(i+j)//2]=="B":
                        ans-=1  
print(ans)

                
                
            
            
            
                            
                


### FIXED CODE ###

def main():
    n=int(input())
    s=list(input())
    ans=0
    how_r=[0 for i in range(n+1)]
    how_g=[0 for i in range(n+1)]
    how_b=[0 for i in range(n+1)]
    for i in range(n):
        string=s[i]
        if string=="R":
            how_r[i+1]+=1
        elif string=="G":
            how_g[i+1]+=1
        elif string=="B":
            how_b[i+1]+=1
    for i in range(n):
        how_r[i+1]+=how_r[i]
        how_g[i+1]+=how_g[i]
        how_b[i+1]+=how_b[i]


    for  i in range(n):
        for j in range(i+1,n):
            x=s[i]
            y=s[j]
            if x!=y:
                if "R" not in [x,y]:
                    ans+=how_r[j+1]-how_r[i]
                    if (i+j)%2==0:
                        if s[(i+j)//2]=="R":
                            ans-=1

                elif "G" not in [x,y]:
                    ans+=how_g[j+1]-how_g[i]
                    if (i+j)%2==0:
                        if s[(i+j)//2]=="G":
                            ans-=1

                elif "B" not in [x,y]:
                    ans+=how_b[j+1]-how_b[i]
                    if (i+j)%2==0:
                        if s[(i+j)//2]=="B":
                            ans-=1  
    print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

N=int(input())
S=input()

ans=0
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] and (j-i)!=(k-j):
        ans+=1

print(ans)


### FIXED CODE ###

from collections import *

N=int(input())
S=input()
c=Counter(S)

ans=c['R']*c['G']*c['B']

for i in range(1,N//2+1):
  for j in range(i,N-i):
    if S[j-i]!=S[j] and S[j]!=S[j+i] and S[j+i]!=S[j-i]:
      ans-=1

print(ans)