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

import sys
sys.setrecursionlimit(2*(10**5)+1)
def make_tree(node):
    global cnt
    cnt += 1
    for i in tree_list[node]:
        if i == tree_dic[node]["p"]:
            continue
        tree_dic[node]["c"].append(i)
        tree_dic[i]["p"] = node
        make_tree(i)

cnt = 0
n, q = map(int, input().split())
tree_list = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree_list[a-1].append(b-1)
    tree_list[b-1].append(a-1)

tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": -1, "c": [], "x": 0}

make_tree(0)

for i in range(q):
    p, x = map(int, input().split())
    tree_dic[p-1]["x"] += x
# print(tree_dic)

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")


### FIXED CODE ###

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

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

tree = [[] for _ in range(n)]

app = set([0])

import queue
next = queue.Queue()
next.put(0)
# print(tree_candidate)
while not next.empty():
    i = next.get()
    for j in tree_candidate[i]:
        if not j in app:
            tree[i].append(j)
            app.add(j)
            next.put(j)

cnts = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    cnts[p-1] += x
    # print(x, p, tree[p-1], cnts)

next = queue.Queue()
next.put(0)

while not next.empty():
    i = next.get()
    for j in tree[i]:
        cnts[j] += cnts[i]
        next.put(j)

for i in cnts:
    print(i, end=' ')
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = max(a)+1
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in a]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+2 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    f = list(set(a))
    f.sort()
    c = [bisect.bisect_left(f,i) for i in a]
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = len(f)
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in c]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+1 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print(f[l])
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
b=[None]*m
c=[None]*m
for i in range(m):
    b[i],c[i] = map(int, input().split(" "))
for i in range(0, m):
    if c[i] < a[0]:
        continue
    a[0:b[i]] = list(map(lambda x: x if c[i] < x else c[i], a[0:b[i]]))
    a.sort()
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

import numpy as np
n= int(input())
s = input()
na = np.zeros(n)
for i in range(n):
  na[i] = int(s[i])
ans = set()
h = set()
for i in range(n-2):
  if na[i] not in h:
    h.add(na[i])
    for j in range(i+1,n-1):
      for k in range(j+1,n):
        tmp = str(na[i]) + str(na[j]) + str(na[k])
        if tmp not in ans:
          ans.add(tmp)
print(len(ans))

### FIXED CODE ###

n= int(input())
s = input()
ans = 0
h = set()
for i in range(n-2):
  ten = set()
  if s[i] not in h:
    h.add(s[i])
    for j in range(i+1,n-1):
      if s[j] not in ten:
        ten.add(s[j])
        ans += len(set(s[j+1:]))
print(ans)
### BUGGY CODE ###

num = input().split(" ")
zahyou = input().split(" ")
zahyou_int = [int(i) for i in zahyou]
num[0] = int(num[0])
num[1] = int(num[1])

rousoku = []
time = 3 * 10 ** 8
for i in range(num[0]-num[1]+1):
    rousoku = zahyou_int[i:(i+num[1])]
    # print(rousoku)
    time_p = -min(0, min(rousoku)) * 2 + max(rousoku)
    time_m = max(0, max(rousoku)) * 2 - min(rousoku)
    if(min(time_p, time_m) < time):
        time = min(time_p, time_m)

print(time)


### FIXED CODE ###

num = input().split(" ")
zahyou = input().split(" ")
zahyou_int = [int(i) for i in zahyou]
num[0] = int(num[0])
num[1] = int(num[1])

rousoku = []
flag = 1
time = 3 * 10 ** 8
for i in range(num[0]-num[1]+1):
    rousoku_min = zahyou_int[i]
    rousoku_max = zahyou_int[(i+num[1]-1)]
    if(flag == 0):
        break
    elif(rousoku_min > 0):
        flag = 0
    time_p = -min(0, rousoku_min) * 2 + rousoku_max
    time_m = max(0, rousoku_max) * 2 - rousoku_min
    if(min(time_p, time_m) < time):
        time = min(time_p, time_m)

print(time)
### BUGGY CODE ###

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

for i in range(n):
    ans = 0
    tmp = 0
    for j in range(n):
        if j != i:
            ans += abs(tmp - a[j])
            tmp = a[j]

    ans += abs(tmp - 0)
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = abs(a[0])

for i in range(n - 1):
    s += abs(a[i] - a[i + 1])
s += abs(a[n - 1])

for i in range(n):
    if i == 0:
        print(s + abs(0 - a[i + 1]) - (abs(0 - a[i]) + abs(a[i] - a[i + 1])))
    elif i == n - 1:
        print(s + abs(a[i - 1] - 0) - (abs(a[i - 1] - a[i]) + abs(a[i])))
    else:
        print(s + abs(a[i - 1] - a[i + 1]) - (abs(a[i - 1] - a[i]) + abs(a[i] - a[i + 1])))
### BUGGY CODE ###

import heapq
def prim(g, v):
    for vi in range(v):
        g[vi].sort()
    
    cost = 0
    heap = iter(g[0])
    rest_tree = set(range(1, v))
    while rest_tree:
        d, u = next(heap)
        if u in rest_tree:
            cost += d
            rest_tree -= {u}
            heap = heapq.merge(heap, g[u])
    return cost

from sys import stdin
readline = stdin.readline


v, e = map(int, readline().split())
from collections import defaultdict
g = defaultdict(list)
for _ in range(e):
    s, t, d = map(int, readline().split())
    g[s].append((d, t))
    g[t].append((d, s))

print(prim(g, v))

### FIXED CODE ###

def kruskal(g, size):
    g.sort(key=itemgetter(2), reverse=True)
    uf = union_find(size)
    tree = []
    while len(tree) < size - 1:
        u, v, d = g.pop()
        if not uf.union(u, v):
            tree.append((u, v, d))
    return tree

class union_find:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:return True
        
        if self.table[y] < self.table[x]:x, y = y, x

        self.table[x] += self.table[y]
        self.table[y] = x
        return False
            
    def find(self, x):
        if self.table[x] < 0:return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]

from sys import stdin
from operator import itemgetter

import heapq

readline = stdin.readline


v, e = map(int, readline().split())

g = [list(map(int, readline().split())) for _ in range(e)]

tree = kruskal(g, v)

print(sum(d for s, t, d in tree))
### BUGGY CODE ###

from collections import deque

n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for i in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = deque()
    newque = deque()
    check = [False for i in range(n)]
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]==True:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
        newque = deque()
    M = max(M,count)
print(n-M)

### FIXED CODE ###

n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for _ in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    check = [False]*n
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        newque = []
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
    M = max(M,count)
print(n-M)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = 10 ** 10
for i in range(n-k+1):
  ans = min(ans, (max(h[i:i+k])-min(h[i:i+k])))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = 10 ** 10
for i in range(n-k+1):
  ans = min(ans, h[i+k-1] - h[i])
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
wvs = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N)]

for i, wv in enumerate(wvs):
    for j in range(W+1):
        if i == 0:
            if wv[0] < j+1:
                dp[0][j] = wv[1]
        elif wv[0] < j+1:
            dp[i][j] = max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[-1]))

### FIXED CODE ###

N, W = map(int, input().split())
wvs = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N)]

for i, wv in enumerate(wvs):
    for j in range(W+1):
        if i == 0:
            if wv[0] < j+1:
                dp[0][j] = wv[1]
        elif wv[0] < j+1:
            dp[i][j] = max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

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

from  heapq import heappush, heappop, heapify

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

nl=[ [ ] for j in range(n+1) ] 

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


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while Q:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print(10**15-i)

### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions
import numpy as np

mod = 10**9+7

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

div = a[0]
for i in range(1, n):
    div = div*a[i]//fractions.gcd(div, a[i])

np_a = np.array(a)
ans = div//np_a
print(np.sum(ans)%mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in a[1:]:
    div = div*i//fractions.gcd(div, i)

ans = 0
for i in a:
    ans += div//i

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

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

sum_of_product = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        sum_of_product += A[i] * A[j]
        if sum_of_product >= 10 ** 9 + 7:
            sum_of_product %= 10 ** 9 + 7

print(sum_of_product)

### FIXED CODE ###

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

sum_list = sum(A)
sum_of_product = 0

for i in A:
    sum_list -= i
    sum_of_product = ((sum_list * i) % (10 ** 9 + 7) + sum_of_product) % (10 ** 9 + 7)

print(sum_of_product)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(-x[1]))

from bisect import bisect_left
s = [i for i in range(1,M+1)]
ans = 0
for i in range(N):
  if a[i][0]<=M:
    place = bisect_left(s,a[i][0])
    if place <= len(s)-1:
      s.pop(place)
      ans += a[i][1]
print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(x[0],x[1]))

b = []
for i in range(N):
  b.append([-a[i][1], a[i][0]])

from bisect import bisect_left, bisect_right
import heapq

ans = 0
h = []

for i in range(1,M+1):
  left = bisect_left(a,[i,0])
  right = bisect_right(a,[i,float('inf')])-1
  if right-left>=0:
    for i in range(left,right+1):
      heapq.heappush(h,b[i])
    x = heapq.heappop(h)
    ans += -x[0]
  else:
    if h:
      x = heapq.heappop(h)
      ans += -x[0]

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

import itertools
import math
a = int(input())

def calc(x,y,z,n):
  if(n==x*x+y*y+z*z+x*y+y*z+z*x):
    return True

for i in range(1,a+1):
  l = list(range(1,int(math.sqrt(a))))
  cnt = 0;
  for x,y,z in itertools.product(l, repeat=3):
    if(calc(x,y,z,i)):
      cnt+=1;
  print(cnt)

### FIXED CODE ###

import itertools
import math

a = int(input())
cnt = 0
ans = [0]*100000
l = list(range(1,int(math.sqrt(a))))

for x,y,z in itertools.product(l, repeat=3):
	ans[x*x+y*y+z*z+x*y+y*z+z*x]+=1

for i in range(1,a+1):
    print(ans[i])
### BUGGY CODE ###

MOD = pow(10, 9) + 7
s = list(input())
s.reverse()
def main():

    dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
    if s[0] == "?":
        for i in range(10):
          dp[1][i] = 1
    else:
        dp[1][int(s[0])%13] = 1

    for i in range(2, len(s) + 1):
        for amari in range(13):
            if s[i-1] != "?":
                dp[i][(amari + int(s[i-1]) * pow(10, i-1, 13)) % 13] += (dp[i-1][amari])%MOD
            else:
                for val in range(10):
                    dp[i][(amari + val * pow(10, i - 1, 13)) % 13] += dp[i - 1][amari]%MOD
    print((dp[len(s)][5] %MOD ))

main()

### FIXED CODE ###

MOD = 1000000007
s = [int(x) if x!="?" else -1 for x in input()]
dp = [[0] *  13 for _ in range(len(s))] 

if s[0] == -1:
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
 
table = [ s % 13 for s in range(130)]
for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])
 
        for old_amari in range(13):
            new_amari = (table[old_amari * 10] + value) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (table[old_amari * 10] + value) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
 
    for i in range(len(dp[index])):
        dp[index][i] %= MOD

print(dp[len(s)-1][5])
### BUGGY CODE ###

N,K=map(int,input().split())
ans={}
for n in range(N):
  a,b=map(int,input().split())
  if a in ans.keys():
    ans[a]+=b
  else:
    ans[a]=b
answer=sorted(ans.items(), key=lambda x:x[0])
count=0
for k in range(len(answer)):
  count+=answer[k][1]
  if count>=K:
    print(answer[k][0])
    break


### FIXED CODE ###

N,K=map(int,input().split())
ans={}
for n in range(N):
  a,b=map(int,input().split())
  if a in ans.keys():
    ans[a]+=b
  else:
    ans[a]=b
answer=sorted(ans.items(), key=lambda x:x[0])
count=0
for k in range(len(answer)):
  count+=answer[k][1]
  if count>=K:
    print(answer[k][0])
    break
### BUGGY CODE ###

N,W = map(int,input().split())
weight = []
value = []

for _ in range(N):
  w,v = map(int,input().split())
  weight.append(w)
  value.append(v)

DP = [[0]*(W+1) for _ in range(N+1)]
ret = 0
for i in range(len(weight)):
  for j in range(W+1):
    if j < weight[i]:
      DP[i+1][j] = DP[i][j]
    if j + weight[i] <= W:
      DP[i+1][j+weight[i]] = max(DP[i+1][j+weight[i]],DP[i][j]+value[i])
      ret = max(DP[i+1][j+weight[i]],ret)
print(ret)

### FIXED CODE ###

def dynamicprogramming():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
fir = []
sec = []
ans = n
ansf = n
for i in range(3):
  if a[i]>b[i]:
    sec.append((a[i],b[i]))
    fir.append((n,n))
  else:
    sec.append((n,n))
    fir.append((b[i],a[i]))
for p in range(n//fir[0][1]+1):
  for q in range((n-p*fir[0][1])//fir[1][1]+1):
    rg = n - p*fir[0][1] - q*fir[1][1]
    if rg < 0:
      continue
    res = rg%fir[2][1]
    r = rg//fir[2][1]
    en = p*fir[0][0] + q*fir[1][0] + r*fir[2][0] + res
    if ansf < en:
      ansf = en
for p in range(ansf//sec[0][1]+1):
  for q in range((ansf-p*sec[0][1])//sec[1][1]+1):
    rg = ansf - p*sec[0][1] - q*sec[1][1]
    if rg < 0:
      continue
    res = rg%sec[2][1]
    r = rg//sec[2][1]
    en = p*sec[0][0] + q*sec[1][0] + r*sec[2][0] + res
    if ans < en:
      ans = en
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [0]*(n+1)
fir = []
sec = []
for i in range(3):
  if a[i]>b[i]:
    sec.append((b[i],a[i]))
  else:
    fir.append((a[i],b[i]))
for i in range(1,n+1):
  dp[i] = i
  for x,y in fir:
    if i-x >= 0:
      dp[i] = max(dp[i],dp[i-x]+y)
n = dp[n]
dp = [0]*(n+1)
for i in range(1,n+1):
  dp[i] = i
  for x,y in sec:
    if i-x >= 0:
      dp[i] = max(dp[i],dp[i-x]+y)
print(dp[n])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
AC = [False] * (N-1)
buffer = []
lr =[]
for i in range(Q):
  buffer = list(map(int,input().split()))
  lr.append(buffer)
for i in range(N-1):
  if S[i:i+2] == "AC":
    AC[i] =  True
for q in range(Q):
  sums = 0
  #print(S[lr[q][0]-1:lr[q][1]])
  for i in range(lr[q][1]-lr[q][0]):
    #print(S[(lr[q][0])+i-1])
    if AC[(lr[q][0])+i-1] == True:
      sums +=1
  print(sums)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
AC = [0] * N
buffer = []
lr =[]
for i in range(Q):
  buffer = list(map(int,input().split()))
  lr.append(buffer)
counts = 0
for i in range(N):
  if S[i:i+2] == "AC":
    counts +=1
  AC[i] =  counts
a =[0]
AC = a + AC
for q in range(Q):
  #print(str(lr[q][0])+" "+ str(lr[q][1]))
  print(AC[lr[q][1]-1] - AC[lr[q][0]-1])
### BUGGY CODE ###

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

count = 0
r = []
g = []
b = []

for i in range(n):
    if s[i] == 'R':
        r.append(i)
    if s[i] == 'G':
        g.append(i)
    if s[i] == 'B':
        b.append(i)

for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            rgb = sorted([r[i],g[j],b[k]])
            if rgb[2]-rgb[1] != rgb[1]-rgb[0]:
                count += 1
print(count)


### FIXED CODE ###

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

count = 0
r = []
g = []
b = []

for i in range(n):
    if s[i] == 'R':
        r.append(i)
    if s[i] == 'G':
        g.append(i)
    if s[i] == 'B':
        b.append(i)

count += len(r)*len(g)*len(b)

for i in range(n-2):
    for j in range(i+1,n):
        if j+(j-i) >= n:
            continue
        k = j + (j-i)
        if (s[i] != s[j]) and (s[j] != s[k]) and (s[k] != s[i]):
            count -= 1

print(count)