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

import numpy as np


def main():
    S = input()
    S = S[::-1]
    _T = 'dreamer', 'dream', 'eraser', 'erase'
    T = []
    for t in _T:
        T.append(t[::-1])
    i = 0
    while 1:
        temp = []

        for t in T:
            if S[i:len(t) + i] == t:
                i += len(t)

        for t in T:
            temp.append(t in S[i:])
        if any(temp) == False:
            break
    if len(S) != i:
        print('NO')
    else:
        print('YES')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = input()
    S = S[::-1]
    _T = 'dreamer', 'dream', 'eraser', 'erase'
    T = []
    for t in _T:
        T.append(t[::-1])
    i = 0
    while 1:
        temp = []
        bool = True
        for t in T:
            if S[i:len(t) + i] == t:
                i += len(t)
                bool = False
        if bool:
            break
    if len(S) != i:
        print('NO')
    else:
        print('YES')


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

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

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

#for i,j in enumerate(l):

for i in range(n):
    v = i + l[i]
    j = i + 1
    while(j < n):
        if(v == j-l[j]):
            count = count + 1
            #print(v,j-l[j])
        j = j + 1

print(count)

### FIXED CODE ###

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

a=[]
b={}
ans=0

for i in range(n):
    a.append(i+l[i])
    b[i-l[i]] = b.get(i-l[i],0) + 1

for av in a:
    ans = ans + b.get(av,0)

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

import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    A1= tuple(input())
    dp = [[0]*2 for _ in range(len(A1)+1)]
    dp[0][0]=1
    for i in range(len(A1)):
        if A1[i]=="1":
            dp[i+1][0]=max(dp[i+1][0],dp[i][0]*2)
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]*3+dp[i][0])
        else:
            dp[i+1][0]=max(dp[i+1][0],dp[i][0])
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]*3)
    #print(dp[len(A1)][0]+dp[len(A1)][1]-len(A1)**2)
    print((dp[len(A1)-1][0]+dp[len(A1)-1][1])%(10**9+7))
main()

### FIXED CODE ###

import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    A1= tuple(input())
    dp = [[0]*2 for _ in range(len(A1)+1)]
    dp[0][0]=1
    for i in range(len(A1)):
        if A1[i]=="1":
            dp[i+1][0]=max(dp[i+1][0],dp[i][0]*2)%(10**9+7)
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]*3+dp[i][0])%(10**9+7)
        else:
            dp[i+1][0]=max(dp[i+1][0],dp[i][0])%(10**9+7)
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]*3)%(10**9+7)
    #print(dp[len(A1)][0]+dp[len(A1)][1]-len(A1)**2)
    print((dp[len(A1)-1][0]+dp[len(A1)-1][1])%(10**9+7))
main()
### BUGGY CODE ###

import math


N = int(input())

S = input()

now = 0

ans = 1

for i in range(2*N):

    #print (S[i],ans,now)

    if i == 0 and S[i] == "W":
        ans = 0
        break

    if i == 0 and S[i] == "B":
        now += 1
        continue

    if S[i] == "W":

        if now % 2 != 0:

            now += 1

        else:

            ans *= now
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans *= now

            now -= 1

        else:

            now += 1


    if now < 0:
        ans = 0
        break

    #print (S[i],ans,now)

if now != 0:
    ans = 0

print ((math.factorial(N) * ans) % (10 ** 9 + 7) )


### FIXED CODE ###



N = int(input())

S = input()

now = 0

ans = 1

for i in range(2*N):

    #print (S[i],ans,now)

    if i == 0 and S[i] == "W":
        ans = 0
        break

    if i == 0 and S[i] == "B":
        now += 1
        continue

    if S[i] == "W":

        if now % 2 != 0:

            now += 1

        else:

            ans = (ans * now) % (10 ** 9 + 7)
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans = (ans * now) % (10 ** 9 + 7)

            now -= 1

        else:

            now += 1


    if now < 0:
        ans = 0
        break

    #print (S[i],ans,now)

if now != 0:
    ans = 0

fac = 1
for i in range(N):

    i += 1
    fac = (fac * i) % (10 ** 9 + 7)

print ((fac * ans) % (10 ** 9 + 7) )
### BUGGY CODE ###

import queue
n, m = map(int, input().split())
g = [[0] * n for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in range(n):
        if root[i] <= 0 and g[p][i] > 0:
            q.put(i)
            root[i] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break

if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])




### FIXED CODE ###

import queue
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

#print(g)

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in g[p+1]:
        if root[i-1] <= 0:
            q.put(i-1)
            root[i-1] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break


if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])
### BUGGY CODE ###

N = int(input())

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

#ワーシャルフロイド法で条件を満たすものがあるか確認
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(N):
    for j in range(N):
        is_edge = True
        for k in range(N):
            if i == j or i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]: # A[i][j]はiとjのノードを直接結ぶものではない
                is_edge = False
        if is_edge:
            ans += A[i][j]

print(ans//2) # A[i][j]とA[j][i]が重複してたされているから２で割る

### FIXED CODE ###

N = int(input())

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

#ワーシャルフロイド法で条件を満たすものがあるか確認
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(N-1):
    for j in range(i,N):
        is_edge = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]: # A[i][j]はiとjのノードを直接結ぶものではない
                is_edge = False
        if is_edge:
            ans += A[i][j]

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

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

pos = 0
saidai = 0
for i in range(N-K+1):
  temp = sum(list(map(lambda x: (x+1)/2, p[i:i+K])))
  if saidai < temp:
    saidai = temp
print('{:.12f}'.format(saidai))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
now = sum(p[:K])
saidai = now
for i in range(K, N):
  now -= p[i-K]
  now += p[i]
  if now > saidai:
    saidai = now
 
print('{:.12f}'.format((saidai + K)/2))
### BUGGY CODE ###

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

n,m = map(int, input().split())
  
if m % n == 0:
  print(m//n)
  exit()
  
elif is_prime(m):
  print(1)
  
else:
  ans = 0
  for i in range(1, m//n+1):
    tmp = m - i * n
    if tmp % i == 0 and ans < i:
      ans = i
    i += 1
  print(ans)

### FIXED CODE ###

n,m = map(int, input().split()) 

ans = 1

for i in range(1, int(m ** 0.5)+1):
  if m % i == 0:
    if i >= n:
      ans = max(ans, m // i)
    elif m // i >= n:
      ans = max(ans, i)
      
      
print(ans)
### BUGGY CODE ###

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

T = 0
for i in range(1,n+1)[::-1]:
  t = (a*i)//b - a*(i//b)
  if T < t:
    T = t

print(T)

### FIXED CODE ###

a,b,n = list(map(int, input().split()))
t = 0
n = min(b-1,n)

print((a*n)//b - a*(n//b))
### BUGGY CODE ###

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().strip()))
    dp = [0] * n
    for i in range(n):
        for j in range(n-i):
            if not i:
                dp[j] = nums[j]
            else:
                dp[j] = abs(dp[j] - dp[j+1])
    print(dp[0])


### FIXED CODE ###


def twos_in_factorial(n):
    return n - bin(n).count('1')


def parity_of_nCr(n, i):
    """ if odd, return False. """
    f = twos_in_factorial
    return f(n) - f(n-i) - f(i) > 0


if __name__ == "__main__":
    n = int(input())
    nums = list(map(lambda x: int(x) - 1, input().strip()))
    no_one = False
    if 1 not in nums:
        nums = [num // 2 for num in nums]
        no_one = True

    is_odd = False
    for i, num in enumerate(nums):
        if not parity_of_nCr(n-1, i) and num & 1:
            is_odd ^= 1

    if not is_odd:
        print(0)
    else:
        print(1 << no_one)
### BUGGY CODE ###

N = int(input())

input_1 = input()
input_2 = input_1.split()

for k in range(N):
    A = map(int, input_2)

    def equal(num):
        return num / 1
    A = [equal(x) for x in A]

    ans = 0

    A.remove(A[k])

    for l in range(N - 1):
        for m in range(N - 1):
            if A[l] == A[m]:
                ans += 1
        
        ans -= 1

    ans = ans / 2

    print(int(ans))


### FIXED CODE ###

#TLE
n = int(input())
a = input().split()
ans = 0
import collections
dic = collections.Counter(a)
for i in dic.values():
    ans += i * (i-1)
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]] + 1))
### BUGGY CODE ###

import math
ans=0

K=int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      num=math.gcd(i,j)
      ans+=math.gcd(num,k)
print(ans)

### FIXED CODE ###

import math
ans=0

K=int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    num=math.gcd(i,j)
    for k in range(1,K+1):
      if num==1:
        ans+=1
      else:
        ans+=math.gcd(num,k)
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

n=int(input())
l=sorted(list(map(int,input().split())))

ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=bisect_left(l[j+1:], l[i]+l[j])

print(ans)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)
 
print(ans)
### BUGGY CODE ###

N, A, *x = map(int, open(0).read().split())

c_nx = N * max(x + [A])
dp = [[[0] * (c_nx + 1) for _ in range(N + 1)] 
      for _ in range(N + 1)]
x = [0] + x

dp[0][0][0] = 1
for j in range(1, N + 1):
    for k in range(N + 1):
        for s in range(c_nx + 1):
            if s < x[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= x[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]]
                
print(sum(dp[N][k][k * A] for k in range(1, N + 1)))

### FIXED CODE ###

N, A, *x = map(int, open(0).read().split())

c_nx = N * max(x + [A])
dp = [[[0] * (c_nx + 1) for _ in range(N + 1)] 
      for _ in range(N + 1)]
x = [0] + x

dp[0][0][0] = 1
for j in range(1, N + 1):
    for k in range(N + 1):
        for s in range(c_nx + 1):
            if s < x[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= x[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]]
                
print(sum(dp[N][k][k * A] for k in range(1, N + 1)))
### BUGGY CODE ###

N,K,Q=map(int,input().split())
score=[K]*N
A=[]
for _ in range(Q):
    A.append(int(input()))
for i in A:
    for j in range(i-1):
        score[j]-=1
    for k in range(i,N):
        score[k]-=1
for s in score:
    if s>0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n, k, q = map(int, input().split())
points = [k] * n
a = []
for i in range(q):
    a.append(int(input())-1)
for cand in a:
    points[cand] += 1
points = [i-q for i in points]
ans = ["Yes" if i > 0 else "No" for i in points]
print(*ans, sep="\n")
### BUGGY CODE ###

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M

data = [[] for i in range(N + 1)]

for i in range(M):
    P[i], Y[i] = map(int, input().split())
    data[P[i]].append(Y[i])

for key in set(P):
    data[key].sort()

for i in range(M):
    x = data[P[i]].index(Y[i]) + 1
    id_number = "{:06}{:06}".format(P[i], x)
    print(id_number)


### FIXED CODE ###

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M

data = [[] for _ in range(N + 1)]

for i in range(M):
    P[i], Y[i] = map(int, input().split())
    data[P[i]].append(Y[i])

for k in set(P):
    data[k].sort()

x = [{} for _ in range(N + 1)]

for k in set(P):
    c = 0
    for v in data[k]:
        c += 1
        x[k][v] = c

for i in range(M):
    id_number = "{:06}{:06}".format(P[i], x[P[i]][Y[i]])
    print(id_number)
### BUGGY CODE ###

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

ans=0
for i in range(k):
      c=0
      while i<k:
            i=i*2
            c+=1
      ans+=(1/n)*(1/2)**c
print(ans)

### FIXED CODE ###

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

ans=0
for i in range(1,n+1):
    c=0
    while i<k:
        i=i*2
        c+=1
    ans+=(1/n)*(1/2)**c
print(ans)
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

def eratosthenes(lim):
  is_p=[2]*lim

  is_p[0]=0
  is_p[1]=1

  for i in range(2,lim):
    for j in range(i*2,lim,i):
      is_p[j] += 1

  return is_p

lim=n+1
is_p=eratosthenes(lim)

ans=0
for i in range(1,n+1):
  ans+=i*is_p[i]
print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

def eratosthenes(lim):
  is_p=[2]*lim

  is_p[0]=0
  is_p[1]=1

  for i in range(2,lim):
    if 1==1:
#    if is_p[i]==2:
#      cnt=2
      for j in range(i*2,lim,i):
#        cnt+=1
#        is_p[j] = cnt
        is_p[j] += 1

  return is_p

lim=n+1
is_p=eratosthenes(lim)

#print(is_p)

ans=0
for i in range(1,n+1):
  ans+=i*is_p[i]
print(ans)
### BUGGY CODE ###

import numpy as np

N, C = map(int, input().split(' '))
s = []
t = []
for i in range(N):
    s_i, t_i, c_i = map(int, input().split(' '))
    s.append(s_i)
    t.append(t_i)
T = max(t)
table = np.zeros(2*T)
schedule = np.zeros(2*T)
for i in range(N):
    schedule[:] = 0
    schedule[2*s[i]-1: 2*t[i]] = 1
    table += schedule
print(int(np.max(table)))

### FIXED CODE ###

import numpy as np

import numpy as np

N, C = map(int, input().split(' '))
s = []
t = []
c = []
for i in range(N):
    s_i, t_i, c_i = map(int, input().split(' '))
    s.append(s_i)
    t.append(t_i)
    c.append(c_i - 1)
T = 2*max(t)
# for i in range(N):
#     table[2*s[i]-1: 2*t[i]] += 1
table = np.zeros(T)
for i in range(C):
    table_i = np.zeros(T)
    for j in range(N):
        if c[j] == i:
            table_i[2*s[j]-1: 2*t[j]] = 1
    table += table_i
print(int(np.max(table)))
### BUGGY CODE ###

N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
num = min(N,M)
C= [None]*(num*2)
C[::2] = A[:num]
C[1::2] = B[:num]
C.extend(A[num:])
C.extend(B[num:])
if N>M:
  C.extend(A[N-M:N])
elif M>N:
  C.extend(B[M-N:M])
  
if min(C[0],C[1])>K:
  print('0')
  exit()
k=0
ans=0
for i in range(len(C)):
  key=min(C[0],C[1])
  k+=key
  ans+=1
  C.remove(key)
  if k>=K:
    break
  if len(C)==1:
    k+=C[0]
    ans+=1
    break
if k==K:
  print(ans)
else:
  print(ans-1)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
     break
  else:
    while b[j] > K - a[i]:
      j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

x = input()

while True:
    n = len(x)
    fl = 0
    for i in range(n-1):
        if x[i] == "S" and x[i+1] == "T":
            x = x[:i] + x[i+2:]
            fl = 1
            break
            
    if fl == 0:
        break
        
print(len(x))

### FIXED CODE ###

from collections import deque
x = input()
n = len(x)
st = deque()

for i in range(n):
    if x[i] == "S":
        st.append("S")
    else:
        if st == deque([]):
            st.append("T")
        else:
            a = st.pop()
            if a == "T":
                st.append("T")
                st.append("T")
            else:
                continue
                
print(len(st))
### BUGGY CODE ###

import bisect

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

a.sort()

for i in range(m) :
  a[n-1] = a[n-1]//2
  b = a[0:n-1]
  index = bisect.bisect_right(b,a[n-1])
  a.insert(index,a[n-1])
  del a[-1]

print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n) :
  a[i] *= -1

heapq.heapify(a)
for i in range(m) :
  at = -1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a, at)

print(sum(a)*-1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0 for i in range(N)]
for i in range(N):
  ans[i]=(A.index(i+1))+1
print(*ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Answer=[0 for i in range(N)]
for t in range(N):
  Answer[A[t]-1]=t+1
print(*Answer)
### BUGGY CODE ###

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    for j in range(i):
        d = INF * 2
        for k in range(N):
            d = min(d, A[i][k] + A[k][j])

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)


### FIXED CODE ###

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

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

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

# N本 まで使うか 10^4
dp=[0] * (N+1)

cost =[0, 2,5,5,4,5,6,3,7,6]

# 桁を追加する→最大のものに桁追加だから、問題なし
# 桁を入れ替える→無駄、初期状態では0桁しかないので単純に足す
# どの桁に追加すればよいか？二分探索をして決める。つまり、最大にしたいので逆順ソート済みにする？不要。先頭と末尾に追加で対応

def digit(x):
  d = 0
  while x % 10 != 0:
    d += 1
    x //= 10
  return d

for i in range(N+1):
    for a in A:
      # i > 0なら何かしら選んでないといけない
       if i + cost[a] <= N and (i == 0 or dp[i] > 0):
        new_i = i + cost[a]
        # 桁求める、数値のまま。桁まで保持しておけば計算の必要ない？そもそも64ビット越えなのでその対処が必要？
        d = digit(dp[i])
        tmp1 = dp[i] + (10** d) * a
        tmp2 = dp[i] * 10 + a
        tmps = [dp[new_i], tmp1, tmp2]
        m = max(tmps)
        dp[new_i] = m
        # print(new_i, tmps, m)

print(dp[N])

### FIXED CODE ###

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

# 0初期化ではダメ。組合せ不可を表し、演算しても問題ない状態にしておく
dp=[-float("inf")] * (N+1)
dp[0]=0

cost =[0, 2,5,5,4,5,6,3,7,6]
for i in range(N+1):
    for a in A:
      # -inf初期化なので、不可能なものの演算結果も同じ
       new_i = i + cost[a]
       if new_i <= N:
        dp[new_i] = max([dp[new_i],  dp[i]+1])

sa = sorted(A, reverse=True)
n = N
ans = 0
while n > 0:
  for a in sa:
    nn = n-cost[a]
    if nn >= 0 and dp[n] == dp[nn] +1:
      ans = ans * 10 + a
      n -= cost[a]
      break

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

from pprint import pprint

n,w = map(int,input().split())

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


dp_table = [[-float("inf")]*(n+1) for _ in range(w+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[before_w][i] = max(dp_table[before_w][i], dp_table[before_w][i-1])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w:
            dp_table[wv[i-1][0]+before_w][i] = max(dp_table[wv[i-1][0]+before_w][i], dp_table[before_w][i-1] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    result = max(result,max(dp_table[y]))

print(result)

### FIXED CODE ###

from pprint import pprint

n,w = map(int,input().split())

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)
### BUGGY CODE ###

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

R = []
G = []
B = []

for i in range(len(S)):
  if S[i] == "R":
    R.append(i)
  elif S[i] == "G":
    G.append(i)
  else:
    B.append(i)

ans = 0

for r in R:
  for g in G:
    for b in B:
      rgb = [r,g,b]
      rgb.sort()
      if rgb[1] - rgb[0] != rgb[2] - rgb[1]:
        ans += 1


print(ans)


### FIXED CODE ###

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

R = 0
G = 0
B = 0

for i in range(len(S)):
  if S[i] == "R":
    R+=1
  elif S[i] == "G":
    G+=1
  else:
    B+=1

ans = R*G*B

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

print(ans)