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

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

cnt=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[j]!=s[k] and s[i]!=s[k] and j-i!=k-j:
                cnt +=1

print(cnt)

### FIXED CODE ###

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

ans=s.count("R")*s.count("B")*s.count("G")
for i in range(n):
    for j in range(i,n):
        k=2*j-i
        if k>=n:break
        if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
            ans -=1

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

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

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        b = N-a-i # 0

        if n%2:
            ans += b*(2**j)
        else:
            ans += a*(2**j)
        n//=2
    ans %= mod

print(ans)

### FIXED CODE ###

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

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        if (n>>j)&1:
            a = N-a-i # 0

        ans += a*(1<<j)
    ans %= mod

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

M = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]

    print(solve(m, n))

def solve(m, n):

    fs = list(factors(m))
    table = dict()
    table[1] = dict()

    for f in fs:
        table[1][f] = 1

    h = 1
    for _ in range(1, n.bit_length()):
        row = dict()
        for f in fs:
            for g in fs:
                if f * g > m:
                    break
                row[f * g] = (row.get(f * g, 0) + table[h][f] * table[h][g]) % M
        table[h * 2] = row
        h *= 2

    prev = { 1: 1 }
    result = None
    h = 1
    for _ in range(n.bit_length()):
        if n & h:
            result = dict()
            for f in prev.keys():
                for g in table[h].keys():
                    if f * g <= m:
                        result[f * g] = (result.get(f * g, 0) + prev[f] * table[h][g]) % M
            prev = result
        h *= 2
    return result[m]

def factors(n):
    import itertools

    tail = []
    for i in itertools.count(1):
        if i * i > n:
            break

        m, r = divmod(n, i)
        if r == 0:
            yield i
            if m != i:
                tail.append(m)
    
    for i in tail[::-1]:
        yield i

main()


### FIXED CODE ###

import sys

MOD = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]
    print(solve(m, n))

def solve(m, n):
    factors = list(get_prime_factors(m))
    h = max((c for f, c in factors), default=0)

    table = dict()
    table[1] = [1 for _ in range(h + 1)]

    i = 1
    while i < n:
        j = n & (i - 1)
        table[i * 2] = [0 for _ in range(h + 1)]
        if n & i != 0 and j != 0:
            table[i + j] = [0 for _ in range(h + 1)]
        for x in range(h + 1):
            for y in range(h + 1 - x):
                table[i * 2][x + y] = (table[i * 2][x + y] + table[i][x] * table[i][y]) % MOD
                if n & i != 0 and j != 0:
                    table[i + j][x + y] = (table[i + j][x + y] + table[i][x] * table[j][y]) % MOD

        if n & i == 0:
            del table[i]
        if n & i != 0 and j != 0:
            del table[i]
            del table[j]

        i *= 2

    ans = 1
    for f, c in factors:
        ans = ans * table[n][c] % MOD
    return ans

def get_prime_factors(n):
    import itertools

    m = n
    for i in itertools.count(2):
        if i * i > m:
            break

        c = 0
        while True:
            x, y = divmod(m, i)
            if y != 0:
                break
            c += 1
            m = x
        if c != 0:
            yield i, c

    if m != 1:
        yield m, 1


main()
### BUGGY CODE ###

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

conti = True
while conti:
    conti = False
    for count, char in enumerate(s):
        if (count - 1) >= 0 and s[count] == s[count - 1]:
            s = s[:count] + s[count + 1:]
            conti = True
            break

print(len(s))


### FIXED CODE ###

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

conti = True
while conti:
    try:
        conti = False
        for count, char in enumerate(s):
            if (count - 1) >= 0 and s[count] == s[count - 1]:
                s = s[:count] + s[count + 1:]
                conti = True
    except IndexError:
        pass

print(len(s))
### BUGGY CODE ###

N=int(input())
S=[str(input()) for _ in range(N)]
dic=[]
n=0
for i in S:
  m=S.count(i)
  if n<m:
    n=m
    dic=[]
    dic.append(i)
  if n==m:
    n=m
    dic.append(i)
    
for j in sorted(set(dic)):
  print(j)

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[input() for _ in range(n)]

sc=Counter(s).most_common()
max_idx=sc[0][1]

ans=[]
for i,j in sc:
  if j==max_idx:
    ans.append(i)

for ll in sorted(ans):
  print(ll)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
double_As = As*2
idx_dic = {}
idx_lis = [N+1]*(2*N)
for i in range(N*2-1, -1, -1):
    a = double_As[i]
    if a in idx_dic:
        idx_lis[i] = idx_dic[a]+1
    idx_dic[a] = i
doubling = [[0]*N for _ in range(100)]
accum = [[0]*N for _ in range(100)]
doubling[0] = [i%N for i in idx_lis[:N]]
accum[0] = [a-i for i, a in enumerate(idx_lis[:N])]
for i in range(1, 100):
    for j in range(N):
        doubling[i][j] = doubling[i-1][doubling[i-1][j]]
        accum[i][j] = accum[i-1][j] + accum[i-1][doubling[i-1][j]]
now = 0
cum = 0
cnt = 0
for i in range(99, -1, -1):
    if cum + accum[i][now]>N*K:
        continue
    else:
        cum += accum[i][now]
        now = doubling[i][now]
ans = []
while cum<N*K:
    if cum+accum[0][now]<=N*K:
        cum += accum[0][now]
        now = doubling[0][now]
    else:
        ans.append(As[now])
        now += 1
        cum += 1
print(*ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
double_As = As*2
idx_dic = {}
idx_lis = [N+1]*(2*N)
for i in range(N*2-1, -1, -1):
    a = double_As[i]
    if a in idx_dic:
        idx_lis[i] = idx_dic[a]+1
    idx_dic[a] = i
doubling = [[0]*N for _ in range(60)]
accum = [[0]*N for _ in range(60)]
doubling[0] = [i%N for i in idx_lis[:N]]
accum[0] = [a-i for i, a in enumerate(idx_lis[:N])]
for i in range(1, 60):
    for j in range(N):
        doubling[i][j] = doubling[i-1][doubling[i-1][j]]
        accum[i][j] = accum[i-1][j] + accum[i-1][doubling[i-1][j]]
now = 0
cum = 0
cnt = 0
for i in range(59, -1, -1):
    if cum + accum[i][now]>N*K:
        continue
    else:
        cum += accum[i][now]
        now = doubling[i][now]
ans = []
while cum<N*K:
    if cum+accum[0][now]<=N*K:
        cum += accum[0][now]
        now = doubling[0][now]
    else:
        ans.append(As[now])
        now += 1
        cum += 1
print(*ans)
### BUGGY CODE ###

import collections
h,w = map(int, input().split())
s=[input()for _ in range(h)]
r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = [[] for _ in range(h*w)]
    que[0].append([i,j])
    for k in range(h*w):
        if que[k]:
            res = k
            for i,j in que[k]:
                f[i*w+j] =k
                for sr in r:
                    ti = i + sr[0]
                    tj = j + sr[1]
                    if ti>=0 and tj>=0 and ti<h and tj<w:
                        if s[ti][tj] == ".":
                            if f[ti*w+tj] == -1:
                                que[k+1].append([ti,tj])
    return res

res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            res = max(res,bfs(i,j))
print(res)

### FIXED CODE ###

import collections

h, w = map(int, input().split())
s = [input() for _ in range(h)]
r = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(i, j):
    global h, w, r
    f = [-1 for _ in range(h * w)]
    que = [[] for _ in range(h * w)]
    que[0].append([i, j])
    for k in range(h * w):
        if que[k]:
            res = k
            for i, j in que[k]:
                f[i * w + j] = k
                for sr in r:
                    ti = i + sr[0]
                    tj = j + sr[1]
                    if ti >= 0 and tj >= 0 and ti < h and tj < w:
                        if s[ti][tj] == ".":
                            if f[ti * w + tj] == -1:
                                que[k + 1].append([ti, tj])
    return res


fl = 0
for i in range(h):
    if "#" in s[i]:
        fl = 1
        break
if fl == 0:
    print(h + w - 2)
else:
    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                res = max(res, bfs(i, j))
    print(res)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
while 1:
    c-=b
    if a==0  or c==0:
        break
    a -= d
    if a==0  or c==0:
        break
print('Yes' if a>0 else 'No')


### FIXED CODE ###

a,b,c,d=map(int,input().split())
while 1:
    c-=b
    if a<=0  or c<=0:
        break
    a -= d
    if a<=0  or c<=0:
        break
print('Yes' if a>0 else 'No')
### BUGGY CODE ###

N,K = map(int, input().strip().split(' '))
H = list(map(int, input().strip().split(' ')))
min_cost = [float('inf')]*N
min_cost[0] = 0
for i in range(N-1):
  for k in range(1, min(K+1, N-i)):
    min_cost[i+k] = min(min_cost[i+k], min_cost[i]+abs(H[i]-H[i+k]))

print(min_cost[N-1])

### FIXED CODE ###

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

dp = [float('inf')]*N
dp[0] = 0
for i in range(N-1):
  for d in range(1, min(K+1, N-i)):
    dp[i+d] = min(dp[i+d], dp[i]+abs(H[i+d]-H[i]))

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

import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('f1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def g(r, s):
  res = 1
  f = 1
  for i in range(1, r+s+3):
    f *= i
    f %= M

  fs = 1
  for i in range(1, s+2):
    fs *= i
    fs %= M

  fr = 1
  for i in range(1, r+2):
    fr *= i
    fr %= M

  res *= pow(fr, M-2, M)
  res *= pow(fs, M-2, M)

  res *= f
  res %= M
  return res


M = 10 ** 9 + 7
def main():
    r1, c1, r2, c2 = read_int_list()
    res = 0
    res += g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
    res %= M
    print(res)


main()


### FIXED CODE ###

import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('f1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


M = 10 ** 9 + 7
f = [1] * (2*10**6+4)
for i in range(1, 2*10**6+3):
  f[i] = f[i-1] * i
  f[i] %= M


def g(r, s):
  res = 1
  frs = f[r+s+2]
  fs = f[s+1]
  fr = f[r+1]

  res *= pow(fr, M-2, M)
  res *= pow(fs, M-2, M)

  res *= frs
  res %= M
  return res


def main():
    r1, c1, r2, c2 = read_int_list()
    res = 0
    res += g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
    res %= M
    print(res)


main()
### BUGGY CODE ###

from sys import stdin
import bisect
from itertools import accumulate
import numpy as np

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())
li = []
for i in range(1,len(s)+1):
    for j in range(len(s)-i+1):
        li.append(s[j:j+i])
li = list(set(li))
li.sort()
print(li[n-1])

### FIXED CODE ###

from sys import stdin

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())
li = []

for i in range(1,6):
    for j in range(len(s)-i+1):
        li.append(s[j:j+i])
li = list(set(li))
li.sort()
print(li[n-1])
### BUGGY CODE ###

from collections import defaultdict

h, w, m = map(lambda x: int(x), input().split())

y_to_num = defaultdict(int)
x_to_num = defaultdict(int)

# y_indexes = set()
# x_indexes = set()
y_to_sum = defaultdict(set)


for _ in range(m):
    hh, ww = map(lambda x: int(x), input().split())
    y_to_num[hh] += 1
    x_to_num[ww] += 1
    
    y_to_sum[hh].add(hh + ww)
    
# print(y_to_num, x_to_num)
    
# for y, num_y in y_to_num:
#     for x, num_x in x_to_num:

max_num = 0
  
for y in range(h):
    for x in range(w):
        num = y_to_num[y+1] + x_to_num[x+1]
        if x+y+2 in y_to_sum[y+1]:
            num -= 1
        max_num = max(max_num, num)
        
print(max_num)

### FIXED CODE ###

from collections import defaultdict
import sys

h, w, m = map(lambda x: int(x), input().split())

y_to_num = [0] * h
x_to_num = [0] * w
existing_h_to_w = defaultdict(set)


for _ in range(m):
    hh, ww = map(lambda x: int(x), input().split())
    y_to_num[hh-1] += 1
    x_to_num[ww-1] += 1
    existing_h_to_w[hh-1].add(ww-1)

max_vertical_num = max(y_to_num)
max_horizontal_num = max(x_to_num)

y_coor_with_max_num = [i for i, num in enumerate(y_to_num) if num == max_vertical_num]
x_coor_with_max_num = [i for i, num in enumerate(x_to_num) if num == max_horizontal_num]

# print(y_coor_with_max_num, x_coor_with_max_num, existing_h_to_w)

for y in y_coor_with_max_num:
    for x in x_coor_with_max_num:
        if x not in existing_h_to_w[y]:
            print(max_vertical_num + max_horizontal_num)
            sys.exit()

print(max_vertical_num + max_horizontal_num - 1)
### BUGGY CODE ###

N = int(input())
a = []
elements = set()
for i in input().split():
    a.append(int(i))
    elements.add(int(i))
    elements.add(int(i)-1)
    elements.add(int(i)+1)
max_count = 0
for X in elements:
    count = 0
    for num in a:
        if X-1 <= num <= X+1:
            count += 1
    max_count = max(max_count, count)
print(max_count)

### FIXED CODE ###

def dic_counter(dic, num):
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

N = int(input())
dic = {}
for i in input().split():
    dic_counter(dic, int(i)-1)
    dic_counter(dic, int(i))
    dic_counter(dic, int(i)+1)
for _, value in sorted(dic.items(), key=lambda x: -x[1]):
    print(value)
    break
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
 
n,k=mi()
h=li()
dp = [0]*n
for i in range(1,n):
    st = max(0,i-k)
    comp = []
    for j in range(st,i):
        comp.append(dp[j]+abs(h[i] - h[j]))
    dp[i] = min(comp)
print(dp[n-1])

### FIXED CODE ###

mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,k=mi()
h=np.array(li())
dp = np.array([0]*n)
for i in range(1,n):
    st = max(0,i-k)
    dp[i] = min(dp[st:i]+abs(h[i] - h[st:i]))
print(dp[n-1])
### BUGGY CODE ###

#elst...i->j = elst[i]j[]
#vlst...[mincost, ...]
INF = 1000000000

def dyc(n,elst,start,goal):
  vlst = [INF for i in range(n)]
  ulst = [0 for i in range(n)]
  vlst[start] = 0
  while True:
    v = -1
    for i in range(n):
      if(ulst[i] == 0 and (v == -1 or vlst[i] < vlst[v])):
        v = i
    if v == -1:
      break
    ulst[v] = 1
    for i in range(n):
      vlst[i] = min(vlst[i], vlst[v] + elst[v][i])
  if vlst[goal] >= INF:
    print(-1)
  else:
    print(vlst[goal])
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    elst = [[INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dyc(n, elst, lst[1] - 1, lst[2] - 1)
      elif lst[0] == 1:
        elst[lst[1] - 1][lst[2] - 1] = min(lst[3],elst[lst[1] - 1][lst[2] - 1])
        elst[lst[2] - 1][lst[1] - 1] = min(lst[3],elst[lst[2] - 1][lst[1] - 1])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=998244353
ans=(m*pow(m-1,n-1,mod))%mod
cntb=1
for i in range(1,k+1):
    # cntb*=(n-i)//i
    cntb*=(n-i)*pow(i,mod-2,mod)
    ans+=(m*pow(m-1,n-1-i,mod)*cntb)%mod
    ans%=mod
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=998244353
cntb=1
ans=0
for i in range(k+1):
    ans=ans+(((m*pow(m-1,n-1-i,mod))%mod)*cntb)%mod
    ans=ans%mod
    cntb=(cntb*(n-1-i)*pow(i+1,mod-2,mod))%mod
print(ans%mod)
### BUGGY CODE ###

import math
from functools import reduce

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

n = int(input())

total = 0

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            total += gcd(i,j,k)

print(total)

### FIXED CODE ###

import math
import sys

def main():
    n = int(sys.stdin.readline())

    total = 0

    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                total += math.gcd(i, math.gcd(j,k))

    print(total)

main()
### BUGGY CODE ###

N = int(input())
lowid= 0
highid = N-1
print(0,flush=True)
lowsex = input()
if lowsex=='Vacant':
    exit()
print(N-1,flush=True)
highsex = input()
if highsex=='Vacant':
    exit()
while high-low>1:
    midid = (lowid+highid)//2
    print(midid,flush=True)
    midsex = input()
    if midsex=='Vacant':
        exit()
    if (midid-lowid)%2==1 and midsex==lowsex:
        highid = midid
        highsex = midsex
    elif (midid-lowid)%2==0 and midsex!=lowsex:
        highid = midid
        highsex = midsex
    else:
        lowid = midid
        lowsex = midsex

### FIXED CODE ###

N = int(input())
lowid= 0
highid = N-1
print(0)
lowsex = input()
if lowsex=='Vacant':
    exit()
print(N-1)
highsex = input()
if highsex=='Vacant':
    exit()
while highid-lowid>1:
    midid = (lowid+highid)//2
    print(midid)
    midsex = input()
    if midsex=='Vacant':
        exit()
    if (midid-lowid)%2==1 and midsex==lowsex:
        highid = midid
        highsex = midsex
    elif (midid-lowid)%2==0 and midsex!=lowsex:
        highid = midid
        highsex = midsex
    else:
        lowid = midid
        lowsex = midsex
### BUGGY CODE ###

class UnionFind:
  def __init__(self, n):
    self.parents=[i for i in range(n)]
    self.rank=[0]*n

  def find(self, x):
    if self.parents[x]==x:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]

  def unite(self, x, y):
    x=self.find(x)
    y=self.find(y)
    if x!=y:
      if self.rank[x]<self.rank[y]:
        self.parents[x]=y
      else:
        self.parents[y]=x
        if self.rank[x]==self.rank[y]:
          self.rank[x]+=1

  def same(self,x,y):
    return self.find(x)==self.find(y)

N,M=map(int,input().split())
uf=UnionFind(N)
for _ in range(M):
  a,b=map(int,input().split())
  uf.unite(a-1,b-1)
par=uf.parents
ans=0
parset=set(par)
for p in parset:
  s=par.count(p)
  ans=max(ans,s)
print(ans)

### FIXED CODE ###

def find(x):
  if par[x] < 0:
    return x
  else:
    tank = []
    while par[x] >= 0:
      tank.append(x)
      x = par[x]
    for elt in tank:
      par[elt] = x
    return x

def unite(x,y):
  x = find(x)
  y = find(y)
    
  if x == y:
    return False
  else:
    if par[x] > par[y]:
      x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

def same(x,y):
  return find(x) == find(y)

def size(x):
  return -par[find(x)]

N,M=map(int,input().split())
par = [-1]*N
for _ in range(M):
  a,b=map(int,input().split())
  unite(a-1,b-1)
print(-min(par))
### BUGGY CODE ###

#! coding: UTF-8
num = int(input())
#桁数
def digit(x):
    point = 0
    while int(x) > 0:
        x /= 10
        point += 1
    return point
#num=A*Bの時の最小桁数
def Multi(num):
    y = digit(num)
    for A in range(1,num):
        if A*A <= num:
            if num%A == 0:
                B = num/A
                C = max(digit(A),digit(B))
                if y > C:
                    y = C
    print(y)
Multi(num)


### FIXED CODE ###

#! coding: UTF-8
num = int(input())
#桁数
def digit(x):
    point = 0
    while int(x) > 0:
        x /= 10
        point += 1
    return point
#num=A*Bの時の最小桁数
def Multi(num):
    y = digit(num)
    A = 1
    while A*A <= num:
        if num%A == 0:
            B = num/A
            C = max(digit(A),digit(B))
            if y > C:
                y = C
        A += 1
    print(y)
Multi(num)
### BUGGY CODE ###

import sys
n, W = map(int, sys.stdin.readline().split())
#L = [[map(int, sys.stdin.readline().split())] for _ in range(n)]
dp = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
    w, v =map(int, sys.stdin.readline().split())
    for j in range(W+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j])
        if dp[i-1][j] !=0 and j+w<=W:
            dp[i][j+w] = max(dp[i-1][j+w], v+ dp[i-1][j])
            #print(dp, i)
        
    dp[i][w] = max(dp[i-1][w], v)
    

#print(dp)  
print(max(dp[-1]))

### FIXED CODE ###

import sys
n, W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0 for _ in range(W+1)] for _ in range(n)]
for w in range(W+1):
    if w>=L[0][0]:
        dp[0][w] = L[0][1]

#print(dp)
for i in range(1, n):
    for w in range(W+1):
        if w <L[i][0]: #そもそも加えられないとき
            dp[i][w] = dp[i-1][w] #前回の状態を代入。
        else: #加えようとしたら入るとき
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w]) #max(加えた時の価値, 前回の状態)
            
#print(dp)
print(max(dp[-1]))
### BUGGY CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    else:
        Sum = []
        for i in range(n):
            Sum.append(int(input()))
        for i in range(2,n + 1):
            for j in range(n - i + 1):
                Wa = 0
                for k in range(j,j + i):
                    Wa += Sum[k]
                Sum.append(Wa)
        print(max(Sum))

### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    else:
        A = []
        Sum = []
        for i in range(n):
            A.append(int(input()))
        Wa = 0
        for i in range(0,n):
            Wa += A[i]
            Sum.append(Wa)
        for i in range(0 , n):
            for j in range(0 , i):
                Num = Sum[i] - Sum[j]
                Sum.append(Num)
        print(max(Sum))
### BUGGY CODE ###

# 初期入力
N = int(input())
L = list(map(int, input().split()))
L_sorted =sorted(L,reverse=True)

#3本選ぶ組み合わせ,1番長いものに対して、一番短い物2本から比較していくとダメなものが速く選べる
from itertools import combinations
count =0
for i in range(N-2):
    for t in combinations(L_sorted[i+1:], 2):
        if L_sorted[i] < sum(t):
            #print(L_sorted[i],t)
            count +=1

print(count)

### FIXED CODE ###

import bisect

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

count  =0
L.sort()
for i in range(0, N - 1):
  for j in range(i + 1, N):
    index = bisect.bisect_left(L, L[i] + L[j]) #AC:約2.9秒
    count += max(0, index - j - 1)

"""
    失敗:回答は出るがTLE:ランダム配列1000本で約6.2秒
    index = bisect.bisect_left(L[j+1:],L[i] + L[j]) #TLEの原因?
    count += index
"""
print(count)