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

import sys
sys.setrecursionlimit(10000000)

f_inf = float("inf") # sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

max_num_sum = (N * (N + 1)) // 2
max_even = N // 2
max_odd = N - max_even

# def solve(pos, cnt, num_sum):
#     global cost

#     if not(pos in ABC_d): return
#     if cnt > N or num_sum > max_num_sum:
#         cost[pos-1] = f_inf;

#     for B, C in ABC_d[pos]:
#         if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
#             pass
#         elif cost[B - 1] < cost[pos - 1] + C:
#             cost[B - 1] = cost[pos - 1] + C
#             solve(B, cnt + 1, num_sum + B)

def solve(pos, odd_cnt, even_cnt, num_sum):
    global cost

    if not(pos in ABC_d): return

    if odd_cnt > max_odd or even_cnt > max_even or num_sum > max_num_sum:
        cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[B - 1] < cost[pos - 1] + C:
            odd_cnt2 = odd_cnt
            even_cnt2 = even_cnt
            if B%2: odd_cnt2 += 1
            else: even_cnt2 += 1
            cost[B - 1] = cost[pos - 1] + C
            solve(B, odd_cnt2, even_cnt2, num_sum + B)


# solve(1, 1, 1)
solve(1, 1, 0, 1)

if (cost[-1] == f_inf):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(1, N + 1):
    p *= i
print(p % (10 ** 9 + 7))
    

### FIXED CODE ###

N = int(input())
pw = 1 
for i in range(1, N + 1):
    pw = (pw * i) % (10 ** 9 + 7)
print(pw)
### BUGGY CODE ###

#!/usr/bin/env python

import collections

def parse_input():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

if __name__ == "__main__":
    N, A = parse_input()
    for i in range(N):
        counts = collections.defaultdict(int)
        for j in range(N):
            if i == j: continue
            counts[A[j]] += 1
        num = 0
        for c in counts.values():
            num += max((c * (c - 1)) // 2, 0)
        print(num)

### FIXED CODE ###

#!/usr/bin/env python

import collections

def parse_input():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

if __name__ == "__main__":
    N, A = parse_input()
    counts = collections.defaultdict(int)
    for i in range(N):
        counts[A[i]] += 1

    total = 0
    subtracts = collections.defaultdict(int)
    for a, c in counts.items():
        num_patterns = max((c * (c - 1)) // 2, 0)
        subtracts[a] = num_patterns - max(((c - 1) * (c - 2)) // 2, 0)
        total += num_patterns

    for i in range(N):
        print(total - subtracts[A[i]])
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**2, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


#@njit("i4(i4[:], i4[:], i4, i4[:])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for bits in range(1 << len(vs)):
        for i in range(len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

N,M = map(int,input().split())
L = list(map(int,input().split()))
for j in range(M):
    idx = L.index(max(L))
    L[idx] //=  2
    
print(sum(L))

### FIXED CODE ###

import heapq

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

q=[]
for l in L:
    heapq.heappush(q, -l)

for _ in range(M):
    p = -heapq.heappop(q)//2
    heapq.heappush(q, -p)

print(-sum(q))
### BUGGY CODE ###

N,X,Y=map(int,input().split())
cost=[[] for _ in range(N)]

for i in range(N-1):
  cost[i].append(i+1)
for j in range(1,N):
  cost[j].append(j-1)

cost[X-1].append(Y-1)
cost[Y-1].append(X-1)
#print(cost)

def bfs(v):
    d=[-1]*N
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in cost[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
        #print(d,q)
    return d

d=dict()
for m in range(N):
  tmp=bfs(m)
  #print(tmp)
  for num in tmp:
    if num not in d:
      d[num]=1
    else:
      d[num] += 1
#print(d)

for z in range(1,N):
  if z in d:
    print(d[z]//2)
  else:
    print(0)

### FIXED CODE ###

N,X,Y=map(int,input().split())
cost=[[] for _ in range(N)]

for i in range(N-1):
  cost[i].append(i+1)
for j in range(1,N):
  cost[j].append(j-1)

cost[X-1].append(Y-1)
cost[Y-1].append(X-1)
#print(cost)

def bfs(v):
    d=[-1]*N
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in cost[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
        #print(d,q)
    return d

d=dict()
for m in range(N):
  tmp=bfs(m)
  #print(tmp)
  for num in tmp:
    if num not in d:
      d[num]=1
    else:
      d[num] += 1
#print(d)

for z in range(1,N):
  if z in d:
    print(d[z]//2)
  else:
    print(0)
### BUGGY CODE ###

print(sum(range(1,int(input()))))

### FIXED CODE ###

N = int(input())
print((N-1) * N // 2)
### BUGGY CODE ###

n = int(input())
listA = list(map(int,input().split()))
count = 0
for k in range(n):
  a = listA[k]
  listA.pop(k)
  #print(listA)
  #Aはset型で数の種類調べる
  A = list(set(listA))
  #print(A)
  for i in A:
    c = listA.count(i)
    #print(c)
    count += int(c*(c-1)/2)
  print(count)
  listA.insert(k,a)
  count = 0
  #print(listA)

### FIXED CODE ###

from collections import Counter
n = int(input())
su = 0
l = list(map(int,input().split()))
l1 = Counter(l)
for k in l1.values():
  su += k*(k-1)//2
for t in l:
  a = l1[t]
  q = su-a*(a-1)//2+(a-1)*(a-2)//2
  print(q)
### BUGGY CODE ###

n = int(input())
A = [int(x) for x in input().split()]
ans = 0
mod = 10 ** 9 + 7
for d in range(60):
    # d桁目ごとに考える
    x = 0
    for a in A:
        if (a >> d) & 1:
            x += 1
    ans += x * (n-x) * 2**d
    ans %= mod
print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    ans = 0
    mod = 10 ** 9 + 7
    for d in range(61):
        # d桁目ごとに考える
        x = 0
        for a in A:
            if (a >> d) & 1:
                x += 1
        ans += x * (n-x) * 2**d
        ans %= mod
    print(ans)

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

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

to = [0]
to += list(map(int, input().split()))


circle = [1]
st = -1
while True:
  point = to[circle[-1]]
  if point in circle:
    st = point
    break
  circle.append(point)

l1 = circle.index(st)
l2 = len(circle) - l1

if k < l1:
  print(circle[k])
elif k < l1 + l2:
  print(circle[k])
else:
  div = (k - l1) % l2
  print(circle[l1+div])

### FIXED CODE ###

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

to = [0]
to += list(map(int, input().split()))

passed = [0] * (n + 1)

circle = [1]
st = -1
while True:
  nx = to[circle[-1]]
  if passed[nx] == 1:
    st = nx
    break
  circle.append(nx)
  passed[nx] = 1
  

l1 = circle.index(st)
l2 = len(circle) - l1

if k < l1:
  print(circle[k])
elif k < l1 + l2:
  print(circle[k])
else:
  div = (k - l1) % l2
  print(circle[l1+div])
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
c=0
for i in range(n-1):
    for j in range(i+1, n):
        if a[i]==a[j]:
            c+=1
            break

if c==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
a.sort()
c=0
for i in range(n-1):
    if a[i]==a[i+1]:
        c+=1
        break
if c==0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] -= t * b[j]
            a[i + j] %= p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] *= -i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for j in range(len(fm)):
            r += fm[j] * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))


### FIXED CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))
### BUGGY CODE ###

S = list(input())
last_size = 0
size = len(S)
while True:
    for i in range(0, len(S)-1):
        if S[i] != S[i+1]:
            del S[i+1]
            del S[i]
            break
    if last_size == len(S) or len(S) == 0:
        break
    else:
        last_size = len(S)
print(size-len(S))

### FIXED CODE ###

num = input()
predicted_value = 0
finished = False
i = 1
while i < len(num):
    if num[i] != num[i-1]:
        num = num[:i-1] + num[i+1:]
        predicted_value += 2
        if i > 1:
            i -= 2
        elif i == 1:
            i = 0
    i += 1
print(predicted_value)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# まずA, Bで総当たり、上位K個をスタック
tmp = []
for a in A:
    for b in B:
        tmp.append(a+b)
tmp = sorted(tmp, reverse=True)[:K]
# 残りのc個に対しても総当たり
ans = []
for s in tmp:
    for c in C:
        ans.append(s+c)
ans = sorted(ans, reverse=True)[:K]
for s in ans:
    print(s)


### FIXED CODE ###


X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# まずA, Bで総当たり、上位K個をスタック
tmp = [a+b for a in A for b in B]
tmp.sort(reverse=True)
tmp = tmp[:K]

# 残りのc個に対しても総当たり
ans = [t+c for t in tmp for c in C]
ans.sort(reverse=True)
ans = ans[:K]
for s in ans:
    print(s)
### BUGGY CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    N = int(input())

    x = prime_factorize(N)
    D = []
    for i in range(2 ** len(x)):
        a = format(i, '0{}b'.format(len(x)))
        D.append(a)

    # print(x)
    # print(D)

    mn = 1 + N
    for di in D:
        a = 1
        b = 1
        for i, dii in enumerate(di):
            if dii == '0':
                a = a * x[i]
            else:
                b = b * x[i]

            if a + b > mn:
                break
        mn = min(mn, a + b)
    print(mn - 2)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt, floor

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    N = int(input())

    # x = prime_factorize(N)
    # D = []
    # for i in range(2 ** len(x)):
    #     a = format(i, '0{}b'.format(len(x)))
    #     D.append(a)

    # mn = 1 + N
    # for di in D:
    #     a = 1
    #     b = 1
    #     for i, dii in enumerate(di):
    #         if dii == '0':
    #             a = a * x[i]
    #         else:
    #             b = b * x[i]
    #     mn = min(mn, a + b)
    # print(mn - 2)

    NN = floor(sqrt(N))
    mn = N + 100
    for i in range(1, NN + 1):
        if N % i == 0:
            a = i
            b = N // i
            # print(a, b)
            mn = min(mn, a + b)

    print(mn - 2)

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

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

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

maxval = 0

temp = -1

dic = {}

def expectedval(inp):
	if inp in dic:
		return inp
	res = (1 + inp) /2
	return res

for i in range(n-(k-1)):
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
	else:
		summ = summ - expectedval(plist(i - 1)) + expectedval(plist(i + k))
	maxval = max(summ, maxval)

print(maxval)

### FIXED CODE ###

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

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

maxval = 0

temp = -1

def expectedval(inp):
	return (1 + inp) /2

for i in range(n-(k-1)):
	# print(i, k)
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
		temp = summ
	else:
		# print(plist[i-1], plist[i+k -1], expectedval(plist[i - 1]), expectedval(plist[i + k - 1]))
		summ = temp - expectedval(plist[i - 1]) + expectedval(plist[i + k - 1])
		temp = summ
	# print(summ)
	maxval = max(summ, maxval)

print(maxval)
### BUGGY CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A

def digits2int(c, L, MOD):
    
    return base


def solve(N, A, L=60, MOD=10**9+7):
    # j桁目のビットが1であるものの数を、累積和として記憶
    count_ones = [[0 for j in range(L+1)] for i in range(N+1)]
    for i in range(N):
        for j in range(L):
            count_ones[i+1][j] = count_ones[i][j] + ((A[i] >> j) & 1)
    # A[i] と A[j] (i<j) のxorをとる
    modsum = 0
    for i in range(N-1):
        c = [0 for j in range(L)]
        for j in range(L):
            if ((A[i] >> j) & 1) == 0:
                c[j] = count_ones[N][j] - count_ones[i+1][j]
            else:
                c[j] = (N-i-1) - (count_ones[N][j] - count_ones[i+1][j])
        # digit2int
        for i in range(L):
            if c[i] > 0:
                f = (c[i] << i) % MOD
                modsum = (modsum + f) % MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

### FIXED CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

def sum_dp(l):
	tmp = 0
	for i, x in enumerate(l[N]):
		if i >= sum_a/2:
			tmp = (tmp + x)%mod
	return tmp

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] = (dp[i+1, :] + dp[i, :]*2)%mod # 赤以外に塗り分ける
	dp[i+1, x:] = (dp[i+1, x:] + dp[i, :-x])%mod # 赤に塗り分ける
	dp2[i+1,:] = (dp2[i+1, :] + dp2[i, :])%mod
	dp2[i+1, x:] = (dp2[i+1, x:] + dp2[i, :-x])%mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a//2+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] += dp[i, :]*2 % mod # 赤以外に塗り分ける
	dp[i+1, x:] += dp[i, :-x] % mod # 赤に塗り分ける
	dp2[i+1,:] += dp2[i, :] % mod
	dp2[i+1, x:] += dp2[i, :-x] % mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))
### BUGGY CODE ###

import math
a = [input().rstrip() for _ in range(5)]
a = sorted(a, key=lambda x: x[-1], reverse=True)

while True:
    m = a.pop()
    if m[-1] == '0':
        a.insert(0, m)
    else:
        break

s = sum([math.ceil(int(n) / 10) * 10 for n in a])
s += int(m)

print(s)



### FIXED CODE ###

s = 0
mod = 0
for _ in range(5):
    i = int(input())
    m = i % 10
    if m != 0:
        if mod == 0:
            mod = m
        else:
            mod = min(mod, m)
        s += (i // 10 + 1) * 10
    else:
        s += i
if mod != 0:
    s = s - 10 + mod

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

# D - Integer Cards
# https://atcoder.jp/contests/abc127/tasks/abc127_d

import sys

n, m = list(map(int, sys.stdin.readline().split()))
cards = list(map(int, sys.stdin.readline().split()))
cards.sort()

set = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

# combinations.sort(key = lambda x: x[1], reverse = True)
combinations = []
for b, c in set:
    combinations.extend([c] * b)

combinations.sort(reverse = True)

for i in range(len(combinations)):
    if i > len(cards) or combinations[i] <= cards[i]:
        break
    else:
        cards[i] = combinations[i]

print(sum(cards))

### FIXED CODE ###

# D - Integer Cards
# https://atcoder.jp/contests/abc127/tasks/abc127_d

import sys

n, m = list(map(int, sys.stdin.readline().split()))
cards = list(map(int, sys.stdin.readline().split()))

combinations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

cards.sort()
combinations.sort(key=lambda x: x[1], reverse=True)

i = 0
for b, c in combinations:
    for k in range(i, min(n, i + b)):
        if cards[k] < c:
            cards[k] = c
            i += 1
        else:
            break

print(sum(cards))
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
mx = 0
mx_list = []
for i in range(N-K+1):
    if sum(p[i:i+K]) > mx:
        mx = sum(p[i:i+K])
        mx_list = p[i:i+K]
ans = 0
for i in mx_list:
    ans += (i+1)/2
print('{:.20f}'.format(ans))


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
S = [0]
for i in range(N):
    S.append(S[i] + (p[i]+1)/2)
ans = 0
for i in range(N-K+1):
    tmp = S[i+K] - S[i]
    ans = max(ans, tmp)
print('{:.20f}'.format(ans))
### BUGGY CODE ###

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

A.sort(reverse=True)

for i in range(M):
    A[0] = A[0]/2
    A.sort(reverse=True)

ans = 0
for i in A:
    ans += int(i)

print(ans)



### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda a: int(a)*(-1), input().split()))

heapq.heapify(A)

for i in range(M):
    a = -heapq.heappop(A)//2
    heapq.heappush(A, -a)
    
print(-sum(A))