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

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(n-k+1):
    ans = max(ans, (sum(p[i:i+k])+k)/2)
print(ans)

### FIXED CODE ###

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

s = 0
ans = 0

for i, j in enumerate(p):
    s+= (j+1)/2
    if i == k-1:
        ans = s
    if i > k-1:
        s -= (p[i-k]+1)/2
        ans = max(ans, s)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1,N+1):
    if i not in A:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[N]%(10**9+7))

### FIXED CODE ###

N,M = map(int,input().split())
A = set(int(input()) for _ in range(M))
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[N]%(10**9+7))
### BUGGY CODE ###

def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((2, S+1), dtype=int)
    dp[0, 0] = 2
    if An[0] <= S:
        dp[0, An[0]] = 1

    for n in range(1, N):
        dp[(n)%2, :] *= 0
        for k in range(S + 1):
            dp[n%2, k] = (dp[n%2, k] + dp[(n-1)%2, k] * 2) % 998244353
            if k + An[n] > S:
                continue
            dp[n%2, k+An[n]] = (dp[n%2, k+An[n]] + dp[(n-1)%2, k]) % 998244353

    print(dp[(N-1)%2, S])
                
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((S+1), dtype=int)
    dp[0] = 2
    if An[0] <= S:
        dp[An[0]] = 1

    for n in range(1, N):
        dp *= 2
        dp[An[n]:] += dp[:-An[n]] // 2
        dp %= 998244353

    print(dp[S])
                
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M=map(int,input().split())
A,B=[],[]
for i in range(N):
    x,y=map(int,input().split())
    A.append(x)
    B.append(y)
k=M
c=0
while k>0:
    a=min(A)
    b=B[A.index(a)]
    k=k-b
    if k>0:
        c=c+a*b
    else:
        c=c+a*(k+b)
    A.remove(a)
    B.remove(b)
print(c)

### FIXED CODE ###

N,M=map(int,input().split())
A=[]
for i in range(N):
    A.append(list(map(int,input().split())))
A.sort(key=lambda x:(x[0],x[1]))
C=[A[0][0]*A[0][1]]
D=[A[0][1]]
for i in range(N-1):
    C.append(C[i]+A[i+1][0]*A[i+1][1])
    D.append(D[i]+A[i+1][1])
for i in range(N):
    if M<D[i]:
        print(C[i]-(D[i]-M)*A[i][0])
        break
if M==D[N-1]:
    print(C[N-1])
### BUGGY CODE ###

def take(n, iterable):
    start, end = 0, n
    while True:
        chunk = iterable[start:end]
        if len(chunk) < n:
            raise StopIteration()
        yield chunk
        start += 1
        end += 1
while True:
    num = int(input())
    if not num: break
    data = [int(input()) for _ in range(num)]
    print(max((sum(chunk) for i in range(1,num+1) for chunk in take(i, data))))

### FIXED CODE ###

while True:
    num = int(input())
    if not num: break
    result, tmp = -1e6, 0
    for _ in range(num):
        new = int(input())
        tmp = max(new, new+tmp)
        result = max(tmp, result)
    print(result)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
ans = 0

if N % 2 == 0:
    for i in range(1, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
    print(2 ** (N // 2) % mod)
else:
    for i in range(2, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
    if A.count(0) != 1:
        print(0)
        exit()
    print(2 ** (N // 2) % mod)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
mod = 10 ** 9 + 7
ans = 0
B = []
if N % 2 == 0:
    for i in range(1, N, 2):
        B.append(i)
        B.append(i)
else:
    B.append(0)
    for i in range(2, N, 2):
        B.append(i)
        B.append(i)

if A == B:
    print(2 ** ( N // 2) % mod)
else:
    print(0)
### BUGGY CODE ###

import numpy as np
h,n = map(int,input().split())
dp = [np.inf] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)
print(dp[h])


### FIXED CODE ###

h,n = map(int,input().split())
dp = [int(1e18)] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)
print(dp[h])
### BUGGY CODE ###

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(T):
        ret = 0
        for a, f in zip(A, F):
            ret += max(0, a - T // f)
        return ret <= K

    ok = max(a * f for a, f in zip(A, F))
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid

    print(ok)

sol()


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()
### BUGGY CODE ###

N,H = (int(i) for i in input().split())
a = []
b = [0]
for i in range(N):
    A,B = (int(i) for i in input().split())
    a.append(A)
    b.append(B)
    

count = 0
while H > 0:
    bigb = max(b)
    if bigb > max(a):
        H -= bigb
        b.remove(bigb)
    else:
        H -= max(a)
    count += 1

print(count)

### FIXED CODE ###

N,H = (int(i) for i in input().split())
a = []
b = [0]
for i in range(N):
    A,B = (int(i) for i in input().split())
    a.append(A)
    b.append(B)
    

count = 0
biga = max(a)
bigb = max(b)
b.sort(reverse = True)

while H > 0:
    if bigb > biga:
        count += 1
        H -= bigb
        b.remove(bigb)
        bigb = b[0]        
    else:
        count += H//biga
        H -= (H//biga)*(biga)
        if H != 0:
            count += 1
        break
        

print(count)
### BUGGY CODE ###

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

i=1
gcd=1
while((i**n)<=p):
    if(p%(i**n)==0):
        gcd*=i
        i+=1
print(gcd)

### FIXED CODE ###

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

i=2
gcd=1
if(n>40):
    print(1)
elif(n==1):
    print(p)
else:
    while((i**n)<=p):
        if(p%(i**n)==0):
            #print(i)
            gcd*=i
            p/=(i**n)
            i-=1
        i+=1
        
    print(gcd)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
a = []
b = []
ca = []
cb = []
for i in range(n // 2):
    a.append(l[i * 2])
    b.append(l[i * 2 + 1])
while (len(a) > 0):
    ca.append([a[0], a.count(a[0])])
    a = [s for s in a if not(s == a[0])]
while (len(b) > 0):
    cb.append([b[0], b.count(b[0])])
    b = [s for s in b if not (s == b[0])]
ca.sort(key=lambda x: x[1], reverse=True)
cb.sort(key=lambda x: x[1], reverse=True)
ca_max = ca[0]
cb_max = cb[0]
ca_max_num = ca[0][1]
cb_max_num = cb[0][1]
if ca_max[0] == cb_max[0]:
    if ca_max[1] > cb_max[1]:
        if len(cb) > 1:
            cb_max_num = cb[1][1]
        else:
            cb_max_num = 0
    else:
        if len(ca) > 1:
            ca_max_num = ca[1][1]
        else:
            ca_max_num = 0
print((n // 2) * 2 - ca_max_num - cb_max_num)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
a = {}
b = {}
for i in range(n // 2):
    key_a = l[i * 2]
    key_b = l[i * 2 + 1]
    if key_a in a:
        a[key_a] = a[key_a] + 1
    else:
        a[l[i * 2]] = 1
    if key_b in b:
        b[key_b] = b[key_b] + 1
    else:
        b[key_b] = 1
a = sorted(a.items(), key=lambda x: x[1], reverse=True)
b = sorted(b.items(), key=lambda x: x[1], reverse=True)
# a = list(a.items())
# b = list(b.items())
# print(a)
# print(b)
ca_max = a[0][0]
cb_max = b[0][0]
ca_max_num = a[0][1]
cb_max_num = b[0][1]
same_num = ca_max_num + cb_max_num
if ca_max == cb_max:
    if len(a) > 1:
        next_ca_max = a[1][1]
    else:
        next_ca_max = 0
    if len(b) > 1:
        next_cb_max = b[1][1]
    else:
        next_cb_max = 0
    same_num = max(ca_max_num + next_cb_max, cb_max_num + next_ca_max)
print(n - same_num)
### BUGGY CODE ###

import math
from functools import reduce

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


K=int(input())

S=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      S+=gcd(i,j,k)

print(S)

### FIXED CODE ###

import math

K=int(input())

f=[]

for i in range(1,K+1):
  for j in range(1,K+1):
    s=math.gcd(i, j)
    f.append(s)

S=0
for i in range(1,K+1):
  for j in f:
    S+=math.gcd(i,j)

print(S)
### BUGGY CODE ###

from itertools import combinations

# from math import gcd
import fractions

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

if A >= B:
    A, B = B, A

# 小さい方の約数リストを計算
divA = []
for i in range(1, A // 2 + 1):
    if A % i == 0:
        divA.append(i)
divA.append(A)
div = [n for n in divA if B % n == 0]
Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
def dfs(i, S, d):
    selected = div[i]
    S.add(selected)
    depth = d
    for j in range(i + 1, Ndiv):
        if fractions.gcd(div[i], div[j]) == 1:
            flag = True
            for k in S:
                if fractions.gcd(k, div[j]) != 1:
                    flag = False
                    break
            if flag:
                dj = dfs(j, S, d + 1)
                depth = max(depth, dj)
    return depth

ans = dfs(0, set({}), 1)
print(ans)

### FIXED CODE ###

import math
from itertools import combinations
from collections import defaultdict

# from math import gcd
import fractions

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

def make_prime_list(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def prime_factorization(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        dict_counter = defaultdict(int)
        for prime in prime_list:
            while num % prime == 0:
                dict_counter[prime] += 1
                num //= prime
        if num != 1:
            dict_counter[num] += 1

        dict_counter = dict(dict_counter)

        return dict_counter

if A >= B:
    A, B = B, A

# # 小さい方の約数リストを計算
# divA = []
# for i in range(1, A // 2 + 1):
#     if A % i == 0:
#         divA.append(i)
# divA.append(A)
# div = [n for n in divA if B % n == 0]
# Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
# def dfs(i, S, d):
#     selected = div[i]
#     S.add(selected)
#     depth = d
#     for j in range(i + 1, Ndiv):
#         if fractions.gcd(div[i], div[j]) == 1:
#             flag = True
#             for k in S:
#                 if fractions.gcd(k, div[j]) != 1:
#                     flag = False
#                     break
#             if flag:
#                 dj = dfs(j, S, d + 1)
#                 depth = max(depth, dj)
#     return depth

# ans = dfs(0, set({}), 1)
# print(Ndiv + 1)

lA = prime_factorization(A)
lB = prime_factorization(B)

if not lA or not lB:
    print(1)
    exit()

count = 0
for key in lA:
    if key in lB:
        count += 1
print(count + 1)
### BUGGY CODE ###

import itertools

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

AB = []
for p in itertools.product(A, B):
    AB.append(sum(p))
AB = sorted(AB, reverse=True)[:K]

l = []
for p in itertools.product(AB, C):
    l.append(sum(p))
l = sorted(l, reverse=True)[:K]
for i in range(K):
    print(l[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import bisect

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

A = sorted(A)
B = sorted(B)
C = sorted(C)

ans = 0

for a in A:
    for i in range(bisect.bisect_right(B, a), len(B)):
        cPtn = len(C) - bisect.bisect_right(C, B[i])
        ans += cPtn

print(ans)


### FIXED CODE ###

import bisect

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

A = sorted(A)
B = sorted(B)
C = sorted(C)

ans = 0

for b in B:
    aPtn = bisect.bisect_left(A, b)
    cPtn = len(C) - bisect.bisect_right(C, b)
    ans += aPtn * cPtn

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

#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            List.append([A, B, C])
            if A * Mb == B * Ma:
                cost = min(cost, C)
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

n = int(input())
v = []

for _ in range(n):
    v.append(int(input()))

n_prime = 0
for v_ in v:
    isprime = True

    if v_ <= 1:
        continue

    for i in range(v_):
        if i <= 1:
            continue
        if v_ % i == 0:
            isprime = False
            break

    n_prime = n_prime + isprime

print(n_prime)



### FIXED CODE ###

import math
n = int(input())
v = []

for _ in range(n):
    v.append(int(input()))

n_prime = 0
for v_ in v:
    isprime = True

    if v_ <= 1:
        continue

    for i in range(1+int(math.sqrt(v_))):
        if i <= 1:
            continue
        if v_ % i == 0:
            isprime = False
            break

    n_prime = n_prime + isprime

print(n_prime)
### BUGGY CODE ###

n, m = map(int, input().split())
broken = []
for _ in range(m):
    a = int(input())
    broken.append(a)
    
dp = [0]*(n+2)
mod = 1000000007
dp[n] = 1

for i in range(n-1,-1 , -1):
    if i in broken:
        continue
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)
    

### FIXED CODE ###

n, m = map(int, input().split())
broken=set(int(input()) for _ in range(m))    

dp = [0]*(n+2)
mod = 1000000007
dp[n] = 1

for i in range(n-1,-1 , -1):
    if i in broken:
        continue
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)
### BUGGY CODE ###

from math import gcd
from functools import reduce


k = int(input())

def gcd_(*numbers):
    return reduce(gcd, numbers)

k += 1
ans = 0

#for i in range(1,k):
#    for j in range(i,k):
#        #print(i,j)
#        if i == j:
#            ans += gcd(i,j)
#        else:
#            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range(1,k):
        for h in range(1,k):
            #print(i,j,h)
            ans += gcd_(i,j,h)


print(ans)


### FIXED CODE ###

import math
from functools import reduce


k = int(input())

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

k += 1
ans = 0

for i in range(1,k):
    for j in range(i,k):
        #print(i,j)
        if i == j:
            ans += gcd(i,j)
        else:
            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range((i+1),k):
        for h in range((j+1),k):
            #print(i,j,h)
            ans += gcd(i,j,h)*6


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

N = int(input())

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

c = 0
max_c = 0

for i in range(N-1):
    for j in range(i+1,N):
        if H[i] < H[j]:
            break
        else:
            c += 1
            i += 1
    if max_c < c:
        max_c = c
    c = 0

print(max_c)

### FIXED CODE ###

N = int(input())

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

c = 0
max_c = 0
i = 0

while i < N-1:
    j = i+1
    while j < N:
        if H[i] < H[j]:
            i = j
            break
        else:
            c += 1
            j += 1
            i += 1
    if max_c < c:
        max_c = c
    c = 0

print(max_c)
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())

ans = 0
p = [0,0]
now = [0,0]
p[0] = n%10
p[1] = 10 - n%10
n = n//10
ans = min(p[0], p[1] + 1)
for _ in range(10**6+1):
  if n <= 0:break
  now[0] = min(p[0] + n%10, p[1] + n%10 + 1)
  now[1] = min(p[0] + 10 - n%10, p[1] + 9 - n%10)
  ans = min(now[0], now[1] + 1)
  n = n//10
  p[0],p[1] = now[0],now[1]
print(ans)


### FIXED CODE ###

import sys
n = [int(i) for i in sys.stdin.readline().rstrip()[::-1]]
ans = 0
i = 0
p = [n[i],10 - n[i]]
now = [0,0]
i += 1
ans = min(p[0], p[1] + 1)
for i in range(1,len(n)):
  now[0] = min(p[0] + n[i]%10, p[1] + n[i]%10 + 1)
  now[1] = min(p[0] + 10 - n[i]%10, p[1] + 9 - n[i]%10)
  ans = min(now[0], now[1] + 1)
  p[0],p[1] = now[0],now[1]
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[[set() for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.add(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
M=[]
for i in range(n):
  if i not in y:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print(x+max(M))

### FIXED CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t-i])
print(max(ans))
### BUGGY CODE ###

A, B, M = list(map(int, input().rstrip().split()))
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))

cost_sale=[]
for _ in range(M):
    x, y, c = list(map(int, input().rstrip().split()))
    tot = a[x-1] + b[y-1] - c
    cost_sale.append(tot)
    
cost_raw = [i + j for i in a for j in b]
print(min(cost_sale + cost_raw))

### FIXED CODE ###

A, B, M = list(map(int, input().rstrip().split()))
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))

cost=[]
for _ in range(M):
    x, y, c = list(map(int, input().rstrip().split()))
    tot = a[x-1] + b[y-1] - c
    cost.append(tot)
    
cost.append(min(a)+min(b))
print(min(cost))
### BUGGY CODE ###

s=input()
k=int(input())
ans=[]
for i in range(len(s)):
  for j in range(len(s)):
    ans.append(s[j:])
  s=list(s)
  s.pop()
  s=''.join(s)
ans=list(set(ans))
ans.sort()
print(ans[k-1])

### FIXED CODE ###

s=input()
k=int(input())
ans=[]
for i in range(len(s)):
  for j in range(max(0,len(s)-5),len(s)):
    ans.append(s[j:])
  s=list(s)
  s.pop()
  s=''.join(s)
ans=list(set(ans))
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

n = int(input())
lista = [int(x) for x in input().split()]

d = 10 ** 9 + 7

total = 0
for i in range(n-1):
    for j in range(i+1, n):
        total += (lista[i] * lista[j]) % d
total %= d
print(total)


### FIXED CODE ###

d = 10 ** 9 + 7
n = int(input())
lista = [int(x) for x in input().split()]
for k in lista:
    k %= d

totalJ = sum(lista)

total = 0
for i in range(n-1):
    totalJ -= lista[i]
    total += totalJ * lista[i]
total %= d
print(total)
### BUGGY CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
  a1, b1 = map(int, input().split())
  a.append(a1)
  b.append(b1)

mp = [10 ** 8] * (h + max(a))
mp[0] = 0
for i in range(h):
  for j in range(n):
    mp[i+a[j]] = min(mp[i+a[j]], mp[i] + b[j])

print(min(mp[h:]))


### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
  a1, b1 = map(int, input().split())
  a.append(a1)
  b.append(b1)

mp = [10 ** 8] * (h + max(a))
mp[0] = 0
for i in range(h):
  for j in range(n):
    mp[i+a[j]] = min(mp[i+a[j]], mp[i] + b[j])

print(min(mp[h:]))
### BUGGY CODE ###

e = []
n, m = map(int, input().split())
for i in range(m):
    e.append(tuple(map(int, input().split())))

r = False
for a, b in filter(lambda t: t[0] == 1, e):
    if list(filter(lambda t: t[0] == b and t[1] == n, e)):
        r = True
        break
if r:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())
s = [False] * n
g = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s[b] = True
    if b == n:
        g[a] = True

ans = "IMPOSSIBLE"
for i in range(n):
    if s[i] and g[i]:
        ans = "POSSIBLE"
        break
print(ans)