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

from logging import getLogger, StreamHandler, DEBUG
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)
logger.addHandler(handler)

import sys

def match(s, sw, index, N):
    if s[index]=='o':
        if sw[index]=='S':
            return sw[(index - 1 + N) % N] == sw[(index + 1 + N) % N]
        else:
            return sw[(index - 1 + N) % N] != sw[(index + 1 + N) % N]
    else:
        if sw[index]=='W':
            return sw[(index - 1 + N) % N] == sw[(index + 1 + N) % N]
        else:
            return sw[(index - 1 + N) % N] != sw[(index + 1 + N) % N]


N = int(input())
s = input()


	 
    

for j in range(4):
    sw = ""
    if j%2==0:
        sw+= 'S'
    else:
        sw+= 'W'

    if (int(j/2))%2==0:
        sw+= 'S'
    else:
        sw+= 'W'
    logger.debug(sw)


    for i in range(N-2):
        if (sw[i+1] == 'S' and s[i+1] == 'o') or (sw[i+1] == 'W' and s[i+1] == 'x'):
            sw+=sw[i]
        else:
            if sw[i] == 'S':
                sw+='W'
            else:
                sw+='S'

        logger.debug(sw)

    if match(s,sw,0,N) and match(s,sw,N-1,N):
        print(sw)
        sys.exit()

print(-1)


### FIXED CODE ###

from logging import getLogger, StreamHandler, DEBUG
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)
logger.addHandler(handler)

import sys

def match(s, sw, index, N):
    if s[index]=='o':
        if sw[index]=='S':
            return sw[(index - 1 + N) % N] == sw[(index + 1 + N) % N]
        else:
            return sw[(index - 1 + N) % N] != sw[(index + 1 + N) % N]
    else:
        if sw[index]=='W':
            return sw[(index - 1 + N) % N] == sw[(index + 1 + N) % N]
        else:
            return sw[(index - 1 + N) % N] != sw[(index + 1 + N) % N]


N = int(input())
s = input()


	 
    

for j in range(4):
    sw = ""
    if j%2==0:
        sw+= 'S'
    else:
        sw+= 'W'

    if (int(j/2))%2==0:
        sw+= 'S'
    else:
        sw+= 'W'
#    logger.debug(sw)


    for i in range(N-2):
        if (sw[i+1] == 'S' and s[i+1] == 'o') or (sw[i+1] == 'W' and s[i+1] == 'x'):
            sw+=sw[i]
        else:
            if sw[i] == 'S':
                sw+='W'
            else:
                sw+='S'

#        logger.debug(sw)

    if match(s,sw,0,N) and match(s,sw,N-1,N):
        print(sw)
        sys.exit()

print(-1)
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(100000000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

# n = 2 * 10 ** 5
# k = 2 * 10 ** 5
# ls = [[i + 1, i + 2] for i in range(n - 1)]
# qs = [[i + 1, 10] for i in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

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

def dfs(x, v):
	global ans
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			dfs(nxt, ans[x])

dfs(0, 0)

#print(ws)
#print(ds)

for i in range(n):
	print(ans[i])


### FIXED CODE ###

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

for i in range(0, n):
	for x in ds[i]:
		ws[x] += ws[i]

for i in range(n):
	print(ws[i])
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [10**9] * n
dp[0] = 0
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[j] + abs(h[i] - h[j]), dp[i])
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [10**9] * n
dp[0] = 0
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[j] + abs(h[i] - h[j]), dp[i])
print(dp[-1])
### BUGGY CODE ###

import numpy as np

# 公式解説を見てからやった
# 複数サイクルでき、1-K回移動可能
# N < 5000?多分、O(N * 2N)くらいで行けそうに見えるが。。。

if __name__ == "__main__":

	N,K = map(int,input().split())
	P = np.array( input().split(), int )
	P -= 1
	C = np.array( input().split(), int )


	# 一度計算したサイクル情報を一応キャッシュしておく。。。
	# あんまり意味なさそう
	cycleIDs = np.full( N, -1, int )
	cycleInfs = []


	# print(P)

	ans = -1e10
	cycleID = 0

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

		if cycleIDs[v] != -1:
			currentCycleItemCnt, currentCycleTotal = cycleInfs[ cycleIDs[v] ]
			# print(currentCycleItemCnt, currentCycleTotal)
		else:
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleItemCnt += 1
				currentCycleTotal += C[v]

				v = P[v]
				if v == n:
					# サイクル発見
					cycleInfs.append( (currentCycleItemCnt, currentCycleTotal) )
					cycleID += 1
					break

				# 一応、一度サイクルを計算した頂点については、
				# その頂点の属するサイクルの情報をメモっておく。。。
				cycleIDs[v] = cycleID

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

			# 頂点vにコマが置かれた時の最高スコアを計算し、
			# これまでの最高スコアを上回ったら、これまでの最高スコアを更新する
			procCnt += 1
			currentCycleSumTmp += C[v]
			if K < procCnt:
				break

			cycleLoopCnt = 0
			if procCnt < K and 0 < currentCycleTotal:
				cycleLoopCnt = ( K - procCnt ) // currentCycleItemCnt

			# print("v=", v, "currentCycleSumTmp=", currentCycleSumTmp, procCnt)
			tmp = currentCycleSumTmp + cycleLoopCnt * currentCycleTotal
			ans = max( ans, tmp )

			v = P[v]
			if v == n:
				# サイクル終了
				break

	print(ans)


### FIXED CODE ###

# 公式解説を見てからやった
# 複数サイクルでき、1-K回移動可能
# N < 5000?多分、O(N * 2N)くらいで行けそうに見えるが。。。

if __name__ == "__main__":

	N,K = map(int,input().split())
	P = [ int(p)-1 for p in input().split() ]
	C = list(map(int,input().split()))

	# 一度計算したサイクル情報を一応キャッシュしておく。。。
	# あんまり意味なさそう
	cycleIDs = [ -1 for _ in range(N) ]
	cycleInfs = []


	# print(P)

	ans = -1e10
	cycleID = 0

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

		if cycleIDs[v] != -1:
			currentCycleItemCnt, currentCycleTotal = cycleInfs[ cycleIDs[v] ]
			# print(currentCycleItemCnt, currentCycleTotal)
		else:
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleItemCnt += 1
				currentCycleTotal += C[v]

				v = P[v]
				if v == n:
					# サイクル発見
					cycleInfs.append( (currentCycleItemCnt, currentCycleTotal) )
					cycleID += 1
					break

				# 一応、一度サイクルを計算した頂点については、
				# その頂点の属するサイクルの情報をメモっておく。。。
				cycleIDs[v] = cycleID

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

			# 頂点vにコマが置かれた時の最高スコアを計算し、
			# これまでの最高スコアを上回ったら、これまでの最高スコアを更新する
			procCnt += 1
			currentCycleSumTmp += C[v]
			if K < procCnt:
				break

			cycleLoopCnt = 0
			if procCnt < K and 0 < currentCycleTotal:
				cycleLoopCnt = ( K - procCnt ) // currentCycleItemCnt

			# print("v=", v, "currentCycleSumTmp=", currentCycleSumTmp, procCnt)
			tmp = currentCycleSumTmp + cycleLoopCnt * currentCycleTotal
			ans = max( ans, tmp )

			v = P[v]
			if v == n:
				# サイクル終了
				break

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

N, W = map( int, input().split())
dp = [10**9+1]*(10**5+2)
dp[0] = 0
for _ in range(N):
    w, v = map( int, input().split())
    #iを実現しうる最小のwを更新すればよいのでは
    for i in range(10**5,0,-1):
        if i <= v:
            dp[i] = min( dp[i], w)
        else:
            if dp[i-v] + w <= W:
                dp[i] = min( dp[i-v] + w, dp[i])
print( dp.index(10**9+1)-1)


### FIXED CODE ###

N, W = map( int, input().split())
dp = [10**9+1]*(10**5+2)
dp[0] = 0
for _ in range(N):
    w, v = map( int, input().split())
    #iを実現しうる最小のwを更新すればよいのでは
    for i in range(10**5,0,-1):
        if i <= v:
            dp[i] = min( dp[i], w)
        else:
            if dp[i-v] + w <= W:
                dp[i] = min( dp[i-v] + w, dp[i])
print( dp.index(10**9+1)-1)
### BUGGY CODE ###

N = int(input())
A = [ int(v) for v in input().split(" ") ]

total = 0
for i in range(N):
  for j in range(i+1, N):
    total += A[i] * A[j]

#print(10**9+7)
print(total % (10**9+7))

### FIXED CODE ###

N = int(input())
A = [ int(v) for v in input().split(" ") ]

sum_A = sum(A)
total = 0
for i in range(N):
  sum_A -= A[i]
  total += A[i] * sum_A

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

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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))

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

def F2_GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[pivot],A[rank] = A[rank],A[pivot]
        for row in range(rank+1,len(A)):
            if A[row][col]:
                A[row] = [A[row][j]^A[rank][j] for j in range(len(A[0]))]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

max_digit = len(format(max(A), 'b'))

use_digit = []
ans = 0
for j in range(max_digit)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        use_digit.append(j)

a = [[0]*max_digit for _ in range(N)]
k = 0
for k,j in enumerate(use_digit):
    for i in range(N):
        if A[i]>>j & 1:
            a[i][k] = 1
        else:
            a[i][k] = 0

g = F2_GaussJordan(a,False)

s = 0
for i in range(N):
    s = max(s,s^sum([g[i][j]*2**use_digit[j] for j in range(len(use_digit))]))
ans += 2*s

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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 = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

for i in range(N):
    A[i] &= ~xor

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

def Combi(n, r):
	return int(factorial[n] / factorial[r] / factorial[n-r])
N, A = [int(x) for x in input().rstrip().split()]
x = [int(x) for x in input().rstrip().split()]
# num = [0]*51
# for i in x:
# 	num[i] += 1
# print(2**num[A]-1)
# factorial = [1]
# for i in range(1, 51):
# 	factorial.append(factorial[i-1] * i)
# for i in range(1, A):
X = max(max(x), A)
dp = [[[0]*(N*X+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
	for k in range(N+1):
		for s in range(N*X+1):
			if j == 0 and k == 0 and s == 0:
				dp[j][k][s] = 1
			elif j >= 1 and s < x[j-1]: # 探索先が総和より大きい
				dp[j][k][s] = dp[j-1][k][s]
			elif j >= 1 and k >= 1 and s >= x[j-1]:
				dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
			else:
				dp[j][k][s] = 0
sum = 0
for i in range(N+1):
	sum += dp[N][i][i*A]
print(sum-1)


### FIXED CODE ###

from sys import stdin
input = stdin.readline

N, A = [int(x) for x in input().rstrip().split()]
x = [int(x) for x in input().rstrip().split()]

X = max(max(x), A)
# dp = [[[0]*(N*X+1) for _ in range(N+1)] for _ in range(N+1)]
# for j in range(N+1):
# 	for k in range(N+1):
# 		for s in range(N*X+1):
# 			if j == 0 and k == 0 and s == 0:
# 				dp[j][k][s] = 1
# 			elif j >= 1 and s < x[j-1]: # 探索先が総和より大きい
# 				dp[j][k][s] = dp[j-1][k][s]
# 			elif j >= 1 and k >= 1 and s >= x[j-1]:
# 				dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
# 			else:
# 				dp[j][k][s] = 0
# sum = 0
# for i in range(1, N+1):
# 	sum += dp[N][i][i*A]
# print(sum)

dp = [[0]*(2*N*X+1) for _ in range(N+1)]
y = [0] * len(x)
for i in range(len(x)):
	y[i] = x[i]-A

for j in range(N+1):
	for t in range(2*N*X+1):
		if j == 0 and t == N*X:
			dp[j][t] = 1
		elif j >= 1 and (t-y[j-1] < 0 or t-y[j-1] > 2*N*X):
			dp[j][t] = dp[j-1][t]
		elif j >= 1 and 0 <= t-y[j-1] <= 2*N*X:
			dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
		else:
			dp[j][t] = 0
print(dp[N][N*X]-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
x = list(input())
bit_cnt = x.count('1')

# bitを一つ増やす場合
pos = [0] * n
pos_total = 0

# bitを一つ減らす場合
neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[i] = base%(bit_cnt+1)
    if x[::-1][i] == '1':
        # 同時にmod(bit_cnt+1)の法でトータルを作成
        pos_total = (pos_total + base) % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)
pos = pos[::-1]

base = 1
if bit_cnt == 1:
    # mod取れない
    pass
else:
    for i in range(n):
        neg[i] = base%(bit_cnt-1)
        if x[::-1][i] == '1':
            # 同時にmod(bit_cnt-1)の法でトータルを作成
            neg_total = (neg_total + base) % (bit_cnt-1)
        base = (base*2) % (bit_cnt-1)
    neg = neg[::-1]

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        # memo[n] = ret
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        # コーナーケース：すべてのbitが0となる
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
x = list(input())
bit_cnt = x.count('1')

# bitを一つ増やす場合
pos = [0] * n
pos_total = 0

# bitを一つ減らす場合
neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[-i-1] = base%(bit_cnt+1)
    if x[-i-1] == '1':
        # 同時にmod(bit_cnt+1)の法でトータルを作成
        pos_total = (pos_total + base) % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)

base = 1
if bit_cnt == 1:
    # mod取れない
    pass
else:
    for i in range(n):
        neg[-i-1] = base%(bit_cnt-1)
        if x[-i-1] == '1':
            # 同時にmod(bit_cnt-1)の法でトータルを作成
            neg_total = (neg_total + base) % (bit_cnt-1)
        base = (base*2) % (bit_cnt-1)

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        # memo[n] = ret
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        # コーナーケース：すべてのbitが0となる
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))
### BUGGY CODE ###

n, p = map(int,input().split())
s = str(input())
mods = [(i*10)%p for i in range(p)]
ans = 0
tmp = 0
for i in range(n):
    now = int(s[i])%p
    if not now:
        ans += 1
    for j in range(i+1,n):
        # print(i,j)
        now = int(s[j])%p + mods[now]
        now %= p
        if not now:
            ans += 1

print(ans)

### FIXED CODE ###

n, p = map(int,input().split())
s = str(input())
ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    exit()

tmp = [0] * p
tmp[0] = 1
mod = 0
r = 1
for i in range(1,n+1):
    mod += (int(s[-i]) * r) % p
    mod %= p
    tmp[mod] += 1
    r *= 10
    r %= p

for i in tmp:
    ans += i*(i-1)//2

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

N = int(input())
A = [int(i) for i in input().split()]
S = [A[i] - i for i in range(N)]
T = [-A[i] - i for i in range(N)]
# j > i
# S[j] == T[i]
ans = 0
for j in range(N):
    for i in range(j - 1, -1, -1):
        if S[j] == T[i]:
            ans += 1
print(ans)


### FIXED CODE ###

from _collections import defaultdict
import sys

read = sys.stdin.buffer.read
N = int(input())
A = [int(i) for i in input().split()]
D = defaultdict(int)

for i, a in enumerate(A, 1):
    D[i - a] += 1

ans = 0
for i, a in enumerate(A, 1):
    ans += D[i + a]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
    x, y, z = map(int,input().split())
    adjacent_list[x].append(y)
    adjacent_list[y].append(x)
##結局、グラフが何個あるか数える
finished = set()
ans = 0
def dfs(node):
    global finished
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)

while len(finished) != n:
    for i in range(1,n+1):
        if i not in finished:
            dfs(i)
            ans += 1
        
print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
    x, y, z = map(int,input().split())
    adjacent_list[x].append(y)
    adjacent_list[y].append(x)
##結局、グラフが何個あるか数える
finished = set()
ans = 0
def dfs(node):
    global finished
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)

while len(finished) != n:
    for i in range(1,n+1):
        if i not in finished:
            dfs(i)
            ans += 1
print(ans)
### BUGGY CODE ###

ss = input()[::-1]
sv = ''
mods = {}

for s in ss:
    sv = s + sv
    i = int(sv) % 2019
    try:
        mods[i] += 1
    except KeyError:
        mods[i] = 1

ans = 0
for k,v in mods.items():
    if k == 0:
        ans += 1
    else:
        ans += (v * (v - 1)) // 2

print(ans)

### FIXED CODE ###

s = input()[::-1] # 右からn桁の数についてループを回していきたいので、文字列を反転させる

sum_of_digits = 0 # 余りの値
cnts = [0] * 2019 # 余りの値ごとに余りが同じ値の数を格納する変数。2019で割る場合、余りは0~2018までの2019通りあるので、リストの長さは2019
cnts[0] = 1 # ※1
d = 1 # sum_of_digitsの計算に使う10の累乗値

# まず余りの値ごとに余りが同じ値の数を数える
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019 # ※2
    cnts[sum_of_digits] += 1

# 次に余りの値ごとにその組み合わせを計算し、足し合わせる
ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

import fractions, itertools
from functools import reduce

N = int(input())
A = [int(i) for i in input().split()]

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

ans = 0
comblist = list(itertools.combinations(tuple(A), N-1))
for l in comblist:
    tmp = gcd(l)
    if tmp > ans:
        ans = tmp
print(ans)


### FIXED CODE ###

import fractions

N = int(input())
A = [int(i) for i in input().split()]

L = [0]
for i in range(N):
        L.append(fractions.gcd(L[i], A[i]))

R = [0] * (N+1)
for i in reversed(range(N)):
        R[i] = (fractions.gcd(R[i+1], A[i]))

ans = []
for i in range(N):
        ans.append(fractions.gcd(L[i], R[i+1]))

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

from sys import stdin
from sys import  setrecursionlimit
setrecursionlimit(33000)

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs=[]
for i in range(N):
    [A, B] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(A)
    Bs.append(B)

dp_map = []
for i in range(N+1):
    temp_arr = [-1 for _ in range(H+1)]
    dp_map.append(temp_arr)
#dp_map = [[-1]*(H+1)]*(N+1)
#print(len(dp_map))
#print(len(dp_map[0]))

def DP(i, j):
    if j<=0:
        return 0
    if dp_map[i][j]!=-1:
        return dp_map[i][j]
    
    if i==1:
        dp_map[i][j] = DP(i,j-As[i-1])+Bs[i-1]
        return dp_map[i][j]

    dp_map[i][j] = min(DP(i-1,j),DP(i,j-As[i-1])+Bs[i-1])
    return dp_map[i][j]

print(DP(N,H))

### FIXED CODE ###

from sys import stdin
from sys import  setrecursionlimit
setrecursionlimit(10000)

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs=[]
for i in range(N):
    [A, B] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(A)
    Bs.append(B)

INF = 10**10
dp_map = [[INF]*(H+1) for _ in range(N+1)]

#dp_map[i][j]: i番目の魔法までを使って、最低でもjのダメージを与える時に必要なMP
dp_map[0][0]  = 0
for i in range(N):
    for j in range(H+1):
        if j<As[i]:
            dp_map[i+1][j] = min(dp_map[i+1][0]+Bs[i],dp_map[i][j])
        else:
            dp_map[i+1][j] = min(dp_map[i+1][j-As[i]]+Bs[i] ,dp_map[i][j])

print(dp_map[N][H])
### BUGGY CODE ###

N, W = map(int, input().split()) #N個の製品、Wの制限
P = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W + 1) for _ in range(N)]

for j in range(P[0][0], W+1):
    dp[0][j] = P[0][1]

for i in range(1, N):
    for j in range(1, W + 1):
        if j - P[i][0] < 0:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            continue

        dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                       dp[i-1][j])

print(dp[N-1][W])

### FIXED CODE ###

def main(N, W, P):
    dp = [[0]*(W + 1) for _ in range(N)]
    for j in range(P[0][0], W+1):
        dp[0][j] = P[0][1]

    for i in range(1, N):
        for j in range(1, W + 1):
            if j - P[i][0] < 0:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                continue

            dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                           dp[i-1][j])

    print(dp[N-1][W])

if __name__ == "__main__":
    N, W = map(int, input().split()) #N個の製品、Wの制限
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, P)
### BUGGY CODE ###

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

import numpy as np


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    for i in range(2, N - 2):
        left_cs = list(np.cumsum(A[:i]))
        right_cs = list(np.cumsum(A[i:]))
        for l, v in enumerate(left_cs):
            if v + left_cs[l + 1] >= left_cs[-1]:
                P = left_cs[l]
                Q = left_cs[-1] - P
                break
        for r, v in enumerate(right_cs):
            if v + right_cs[r + 1] >= right_cs[-1]:
                R = right_cs[r]
                S = right_cs[-1] - R
                break
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

### FIXED CODE ###

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

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = list(accumulate(A))
    l = 0
    r = 0
    for i in range(1, N - 2):
        while cs[i] > cs[l] + cs[l+1]:
            l += 1
        while cs[-1] + cs[i] > cs[r] + cs[r+1]:
            r += 1
        P = cs[l]
        Q = cs[i] - P
        R = cs[r] - P - Q
        S = cs[-1] - cs[r]
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

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

from decimal import *
import math
getcontext().prec=100000
a,b,c=map(int,input().split())
if Decimal(a).sqrt()+Decimal(b).sqrt()<Decimal(c).sqrt():
  print("Yes")
else:
  print("No")


### FIXED CODE ###

from decimal import Decimal
import math
a,b,c=map(int,input().split())
if c-a-b>0 and 4*a*b<(c-a-b)**2:
  print("Yes")
else:
  print("No")