Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
size, count = list(map(int,input().split()))
dices = list(map(int,input().split()))

max_num = 0
d_set = dices[0:count]
max_sum = sum(d_set)

for num,d in enumerate(dices[count:]):
    d_set.pop(0)
    d_set.append(d)
    now_sum = sum(d_set)
    if max_sum < now_sum:
        max_sum = now_sum
        max_num = num+1

max_set = dices[max_num: max_num+count]
kitai = sum([(d+1)/2 for d in max_set])
print(kitai)

Fixed submission:
size, count = list(map(int,input().split()))
dices = list(map(int,input().split()))

max_sum = sum(dices[0:count])
now_sum = max_sum

for p,d in zip(dices,dices[count:]):
    now_sum = now_sum - p + d
    if max_sum < now_sum:
        max_sum = now_sum

print((max_sum+count)/2)
Buggy python submission (verdict: Runtime Error):
app, ap_chip = map(int,list(input().split()))


ap_chip += app*3


print(int(ap_chip%2)


Fixed submission:
app, ap_chip = map(int,list(input().split()))


ap_chip += app*3


print(int(ap_chip/2))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()

    if N == 1:
        print(0)
        return
    else:
        print(sum(range(N)))
        return

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()

    if N == 1:
        print(0)
        return
    else:
        print(sum(range(N)))
        return

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calc_comb(zeros, ones, length):
    return (2**ones * 3**(length - ones - zeros)) % MOD

def main():
    # L = int('0b'+SI(), 0)
    L = SI()

    count_one = 0
    count_zero = 0
    comb = 0
    for char in L:
        if char == '0':
            count_zero += 1
        elif char == '1':
            count_one += 1
            comb += calc_comb(count_zero + 1, count_one -1, len(L))
            comb %= MOD

    comb += calc_comb(count_zero, count_one, len(L))  # Lの最後が0だったとしても1だったとしても、a+b = L の場合が計算されていない。
    comb %= MOD

    print(comb)

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calc_comb(zeros, ones, length):
    return (pow(2,ones,MOD) * pow(3,(length - ones - zeros),MOD)) % MOD

def main():
    # L = int('0b'+SI(), 0)
    L = SI()

    count_one = 0
    count_zero = 0
    comb = 0
    for char in L:
        if char == '0':
            count_zero += 1
        elif char == '1':
            count_one += 1
            comb += calc_comb(count_zero + 1, count_one -1, len(L))
            comb %= MOD

    comb += calc_comb(count_zero, count_one, len(L))  # Lの最後が0だったとしても1だったとしても、a+b = L の場合が計算されていない。
    comb %= MOD

    print(comb)

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, M = LI()
A = LI()
BandC = []
for i in range(M):
    BandC.append(LI())

A = sorted(A)
BandC = sorted(BandC, key=lambda x: x[1], reverse=True)

BandC_list = []
for i in BandC:
    BandC_list += [i[1]]*i[0]

ans = 0
for i, a in enumerate(A):
    if i < len(BandC_list):
        ans += max(a, BandC_list[i])
    else:
        ans += a

print(ans)

Fixed submission:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    A = LI()
    BandC = []
    for i in range(M):
        BandC.append(LI())
 
    A = sorted(A)
    BandC = sorted(BandC, key=lambda x: x[1], reverse=True)
 
    BandC_counter = 0
    BandC_position = 0
    BandC_sum = 0
    for A_position in range(N):
        if A[A_position] > BandC[BandC_position][1]:
            break
        BandC_sum += BandC[BandC_position][1]
        BandC_counter += 1
        if BandC_counter >= BandC[BandC_position][0]:
            BandC_position += 1
            BandC_counter = 0
            if BandC_position >= len(BandC):
                A_position += 1
                break
    else:
        A_position += 1
 
    print(BandC_sum + sum(A[A_position:]))

main()
Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache

INF = 10 ** 18
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()
N = len(A_li)

@lru_cache(maxsize=None)
def dp(i,j):
    if i == 0:
        if j == 0: return 0
        elif j == 1: return -INF
    else:
        if j == 0: return max(dp(i-1,0) + A_li[i-1], dp(i-1,1) - A_li[i-1])
        if j == 1: return max(dp(i-1,0) - A_li[i-1], dp(i-1,1) + A_li[i-1])

print(dp(N,0))

Fixed submission:
import sys

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

import numpy as np

A_abs = np.abs(A_li)
A_neg_count = sum([1 if i<0 else 0 for i in A_li])

if 0 in A_li or A_neg_count%2 == 0: print(sum(A_abs))
else: print(sum(A_abs) - 2 * min(A_abs))

Buggy python submission (verdict: Runtime Error):
import sys

INF = 10 ** 18
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()
N = len(A_li)

def dp(i,j):
    if i == 0:
        if j == 0: return 0
        elif j == 1: return -INF
    else:
        if j == 0: return max(dp(i-1,0) + A_li[i-1], dp(i-1,1) - A_li[i-1])
        if j == 1: return max(dp(i-1,0) - A_li[i-1], dp(i-1,1) + A_li[i-1])

print(dp(N,0))


Fixed submission:
import sys

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

import numpy as np

A_abs = np.abs(A_li)
A_neg_count = sum([1 if i<0 else 0 for i in A_li])

if 0 in A_li or A_neg_count%2 == 0: print(sum(A_abs))
else: print(sum(A_abs) - 2 * min(A_abs))

Buggy python submission (verdict: Runtime Error):
import sys

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

def dp(i,j):
    if i == 0:
        if j == 0: return A_li[0]
        elif j == 1: return -A_li[0]
    else:
        if j == 0: return max(dp(i-1, 0) + A_li[i], dp(i-1, 1) - A_li[i])
        if j == 1: return max(dp(i-1, 0) - A_li[i], dp(i-1, 1) + A_li[i])

print(dp(N-1,0))


Fixed submission:
import sys

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

import numpy as np

A_abs = np.abs(A_li)
A_neg_count = sum([1 if i<0 else 0 for i in A_li])

if 0 in A_li or A_neg_count%2 == 0: print(sum(A_abs))
else: print(sum(A_abs) - 2 * min(A_abs))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, K = LI()
S = SI().strip()

searching = 1
count = [0]
head = 0
for i in range(N):
    if int(S[i]) == searching:
        count[head] += 1
    else:
        searching = (searching+1)%2
        head += 1
        count.append(1)
if len(count)//2 <= K:
    print(N)
    sys.exit()

count.append(0)

max_length = 0
for k in range(N):
    if 2*k+2*K+1 > N: break
    max_length = max(sum(count[2*k:2*k+2*K+1]), max_length)
print(max_length)


Fixed submission:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, K = LI()
    S = SI().strip()

    searching = 1
    count = [0]
    head = 0
    for i in range(N):
        if int(S[i]) == searching:
            count[head] += 1
        else:
            searching = (searching+1)%2
            head += 1
            count.append(1)
    if len(count)//2 <= K:
        print(N)
        sys.exit()

    count.append(0)

    current_sum = sum(count[0:2*K+1])
    max_length = current_sum
    try:
        for k in range(1, N):
            if 2*k+2*K > len(count): break
            current_sum = current_sum - count[2*k-2] - count[2*k-1] + count[2*k+2*K-1] + count[2*k+2*K]
            max_length = max(current_sum, max_length)
    except:
        pass
    print(max_length)

main()
Buggy python submission (verdict: Runtime Error):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

li = []
for i in range(5):
    li.append(II())

sum_ = 0
li_mod = []
for i in li:
    if i%10 == 0:
        sum_ += i
    else:
        sum_ += ((i//10)+1)*10
        li_mod.append(10-i%10)
sum_ -= max(li_mod)

print(sum_)


Fixed submission:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

li = []
for i in range(5):
    li.append(II())

sum_ = 0
li_mod = []
for i in li:
    if i%10 == 0:
        sum_ += i
    else:
        sum_ += ((i//10)+1)*10
        li_mod.append(10-i%10)
if li_mod:
    sum_ -= max(li_mod)

print(sum_)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

from functools import lru_cache

def main(): 
    N = II()
    h = LI()

    @lru_cache()
    def min_cost(x):
        if x == 0: return 0
        elif x == 1: return abs(h[1] - h[0])
        else: return min(min_cost(x-1) + abs(h[x] - h[x-1]), min_cost(x-2) + abs(h[x] - h[x-2]))

    print(min_cost(N-1))

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

from functools import lru_cache

def main(): 
    N = II()
    h = LI()

    @lru_cache()
    def min_cost(x):
        if x == 0: return 0
        elif x == 1: return abs(h[1] - h[0])
        else: return min(min_cost(x-1) + abs(h[x] - h[x-1]), min_cost(x-2) + abs(h[x] - h[x-2]))

    print(min_cost(N-1))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def main(): 
    N = II()
    h = LI()

    def min_cost(x):
        if x == 0: return 0
        elif x == 1: return abs(h[1] - h[0])
        else: return min(min_cost(x-1) + abs(h[x] - h[x-1]), min_cost(x-2) + abs(h[x] - h[x-2]))

    print(min_cost(N-1))

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

from functools import lru_cache

def main(): 
    N = II()
    h = LI()

    @lru_cache()
    def min_cost(x):
        if x == 0: return 0
        elif x == 1: return abs(h[1] - h[0])
        else: return min(min_cost(x-1) + abs(h[x] - h[x-1]), min_cost(x-2) + abs(h[x] - h[x-2]))

    print(min_cost(N-1))

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, K = LI()
    h_li = [0] + LI()
    min_cost_li = [INF for _ in range(N+1)]
    min_cost_li[1] = 0

    for i in range(1,N+1):  # 10**5
        for j in range(1, K+1): # 10**2
            if i+j > N: continue
            min_cost_li[i+j] = min(min_cost_li[i+j], min_cost_li[i] + abs(h_li[i] - h_li[i+j]))

    print(min_cost_li[N])

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, K = LI()
    h_li = [0] + LI()
    min_cost_li = [INF for _ in range(N+1)]
    min_cost_li[1] = 0

    for i in range(1,N+1):  # 10**5
        for j in range(1, K+1): # 10**2
            if i+j > N: continue
            min_cost_li[i+j] = min(min_cost_li[i+j], min_cost_li[i] + abs(h_li[i] - h_li[i+j]))

    print(min_cost_li[N])


main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

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

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

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

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main2(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

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

def main():
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    # knapsack_dp[考慮した品物][その重さピッタリの重さ] = 価値 とする。
    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight != w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(max(knapsack_dp[N-1]))

main()

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    wv = []
    for _ in range(N):
        wv.append(LI())


    # 横軸 v, 縦軸 n
    dp_table = [[None for _ in range(10**5+1)] for _ in range(N)]
    
    # init
    w0, v0 = wv[0]
    dp_table[0][0] = 0
    dp_table[0][v0] = w0

    # dp
    for i, item in enumerate(wv):
        if i== 0: continue
        w,v = item
        for val, weight in enumerate(dp_table[i-1]):
            if weight is not None:
                # i番目の荷物を入れないとき
                dp_table[i][val] = min(dp_table[i][val], weight) if dp_table[i][val] is not None else weight
                # i番目の荷物を入れるとき
                dp_table[i][val+v] = weight + w

    v  = 10**5
    for w in reversed(dp_table[N-1]):
        if w and w <= W:
            print(v)
            break
        v -= 1


main()
Buggy python submission (verdict: Runtime Error):
input_array = []
while True:
    try:
        input_array.append(input().split())
    except:
        break
for i in input_array:
    print(int(i[0] + i[1]/2))

Fixed submission:
import sys
input = sys.stdin.readline

input_array = []
input_array.append(input().split())

for i in input_array:
    print(int(int(i[0]) + int(i[1])/2))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
Mod = 10**9 + 7
a.sort()
c = [0] * (n+1)
c[k - 1] = 1
for i in range(n+1):
    if i >= k:
        c[i] = (c[i - 1]*i) // (i - k + 1)
ans = 0
for i in range(1, n + 1):
    ans += (a[i - 1] * (c[i - 1] - c[n - i])) % Mod
print(ans % Mod)

Fixed submission:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
Mod = 10**9 + 7
a.sort()
c = [0] * (n+1)
c[k - 1] = 1
for i in range(n+1):
    if i >= k:
        c[i] = ((c[i - 1]*i * pow(i - k + 1, Mod - 2, Mod))) % Mod
ans = 0
for i in range(1, n + 1):
    ans += (a[i - 1] * (c[i - 1] - c[n - i])) % Mod
print(ans % Mod)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
Mod = 10**9 + 7
a.sort()
c = [0] * (n+1)
c[k - 1] = 1
for i in range(n+1):
    if i >= k:
        c[i] = (c[i - 1]*i) // (i - k + 1)
ans = 0
for i in range(1, n + 1):
    ans += (a[i - 1] * (c[i - 1] - c[n - i])) % Mod
print(ans % Mod)

Fixed submission:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
Mod = 10**9 + 7
a.sort()
c = [0] * (n+1)
c[k - 1] = 1
for i in range(n+1):
    if i >= k:
        c[i] = ((c[i - 1]*i * pow(i - k + 1, Mod - 2, Mod))) % Mod
ans = 0
for i in range(1, n + 1):
    ans += (a[i - 1] * (c[i - 1] - c[n - i])) % Mod
print(ans % Mod)