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

import numpy as np
N,K,Q = map(int,input().split())
Qlist = [int(input()) for _ in range(Q)]
Alist = np.full(N,K)
for i in Qlist:
    Alist[i-1]+=1
    Alist-=1
for A in Alist:
    print("Yes" if A>0 else "No")

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline
N,K,Q = map(int,input().split())
QCounter = Counter([int(input()) for _ in range(Q)]).most_common()
defult_over = Q-K #突破に必要な正解数

if defult_over>=0:
    s = set()
    for win in QCounter:
        if win[1]>defult_over:
            s.add(win[0]-1)
    for i in range(N):
        if i in s:
            print("Yes")
        else:
            print("No")
else:
    for _ in range(N):
        print("Yes")
### BUGGY CODE ###

H,W = map(int,input().split())
A = []

for i in range(H):
    t = list(input())
    A.append(t)

tate = (-1,1,0,0)
yoko = (0,0,-1,1)
answer = 0

def move(i,j):
    for p, q in zip(tate, yoko):
        m = i + p
        n = j + q
        if m >= 0 and m < H:
            if n >= 0 and n < W:
                if A[m][n] == '.':
                    if dp[m][n] > dp[i][j]:
                        dp[m][n] = dp[i][j] + 1
                        move(m,n)

for i in range(H):
    for j in range(W):
        dp = [[10**4 for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            dp[i][j] = 0
            move(i,j)
            for k in range(H):
                for l in range(W):
                    if dp[k][l] < 10**4:
                        answer = max(answer,dp[k][l])

print(answer)

### FIXED CODE ###

H,W = map(int,input().split())
A = []

for i in range(H):
    t = list(input())
    A.append(t)

tate = (-1,1,0,0)
yoko = (0,0,-1,1)
answer = 0

for i in range(H):
    for j in range(W):
        dp = [[10**4 for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            dp[i][j] = 0
            Q = list()
            Q.append([i,j])
            while(len(Q) > 0 ):
                s = Q[0][0]
                t = Q[0][1]
                for p, q in zip(tate, yoko):
                    m = s + p
                    n = t + q
                    if m >= 0 and m < H:
                        if n >= 0 and n < W:
                            if A[m][n] == '.':
                                if dp[m][n] == 10**4 :
                                    dp[m][n] = dp[s][t] + 1
                                    Q.append([m,n])
                Q.remove(Q[0])

            for k in range(H):
                for l in range(W):
                    if dp[k][l] < 10**4:
                        answer = max(answer,dp[k][l])

print(answer)
### BUGGY CODE ###

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

ab = []
ma = 0
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])
    ma = max(ma,a)

dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min([dp[max(i-a,0)]+b for a,b in ab])

print(min(dp[h:]))

### FIXED CODE ###

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

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

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

N = int(input())
 
S = []
for i in range(N):
  S.append(input())

S_set = list(set(S))
S_set.sort()

ans = [["" for i in range(2)] for i in range(len(S_set))]
n = 0
for i in range(len(S_set)):
  count = S.count(S_set[i])
  ans[i][0] = S_set[i]
  ans[i][1] = count
  if n < count:
    n = count
    
for i in range(len(S_set)):
  if ans[i][1] == n:
    print(ans[i][0])


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
 
d = {}
for i in s:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1
        
m = max(d.values())

l = []
for i in d.keys():
  if d[i] == m:
  	l.append(i)
    
l_s = sorted(l)
for i in l_s:
  print(i)
### BUGGY CODE ###

# coding: utf-8
n = int(input())
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

# coding: utf-8
n = int(input())
ans = (n*(n-1))//2
print(ans)
### BUGGY CODE ###

num, point, ques = list(map(int, input().split(" ")))
ans_list = []
point_list = []

for i in range(ques):
    ans_list.append(int(input()))

for i in range(num):
    point_list.append(point)

for ans in ans_list:
    point_list[ans-1]+=1
    for i in range(num):
        point_list[i] -= 1

for i in range(num):
    if(point_list[i]<=0):
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

num, point, ques = list(map(int, input().split(" ")))
ans_list = []
point_list = []

for i in range(num):
    point_list.append(point)

for i in range(ques):
    point_list[int(input())-1]+=1

for i in range(num):
    if(point_list[i]-ques<=0):
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

x,y=list(map(int, input().split()))
z=list(map(int, input().split()))
t=0
for i in range(y):
	t=z.index(max(z))
	z[t]=z[t]//2
print(sum(z))

### FIXED CODE ###

import heapq
x,y=list(map(int, input().split()))
z=list(map(int, input().split()))
z = list(map(lambda x: x*(-1), z))
heapq.heapify(z)
for i in range(y):
	k=heapq.heappop(z)
	heapq.heappush(z, -(-k//2))
z = list(map(lambda x: x*(-1), z))
print(sum(z))
### BUGGY CODE ###

import collections


N = int(input()) #1行目のNを取得する
s = [input() for i in range(N)] #複数行の数値の入力を取得

counted = collections.Counter(s)
#最頻値が同値である場合全て出力したい
#頻出数ではなく、文字だけ出力したい
ret = [letter for letter,count in counted.most_common() if count == counted.most_common()[0][1]]
new_ret=sorted(ret)
[print(i) for i in new_ret]


### FIXED CODE ###

from collections import Counter


N = int(input()) #1行目のNを取得する
s = [input() for i in range(N)] #複数行の数値の入力を取得
ans=[]

counted = Counter(s)#
counted_sort=counted.most_common()

for i in range(len(counted_sort)):
    if counted_sort[i][1]==counted_sort[0][1]:
        ans.append(counted_sort[i][0])


[print(i) for i in sorted(ans)]
### BUGGY CODE ###

def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

### FIXED CODE ###

def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
start = M
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

sum = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        sum += int(a[i] ^ a[j])

print(sum % (10 ** 9 + 7))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

j_max = 0
cnt = [0] * 60
for i in range(n):
    for j in range(60):
        cnt[j] += a[i] % 2
        a[i] = a[i] // 2
        if a[i] == 0:
            j_max = max(j_max, j)
            break

ans = 0
for i in range(j_max + 1):
    ans = (ans + (2 ** i) * cnt[i] * (n - cnt[i])) % mod

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

n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

import bisect
a = [0,0,n+1,n+1]
ans = 0
for tmp in p_ind:
    val, i = tmp
    j = bisect.bisect(a,i)
    ans += ((a[j+1] - a[j])* (i - a[j-1]) + (a[j] - i)* (a[j-1] - a[j-2])) * val
    bisect.insort(a,i)

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

# 平方分割します。
max_n = 10**5
div_n = int(max_n**(1/2))+1
a = [[] for _ in range(div_n)]
a[0] = [0,0]
a[(n+1)//div_n].append(n+1)
a[(n+1)//div_n].append(n+1)
a_count = [0] * (div_n)
a_count[0] += 2
a_count[(n+1)//div_n] += 2

import bisect
ans = 0
for tmp in p_ind:
    val, i = tmp
    group = i//div_n
    j = bisect.bisect(a[group],i)
    #left
    if(j>1):
        left1 = a[group][j-1]
        left2 = a[group][j-2]
    elif(j==1):
        left1 = a[group][j-1]
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        left2 = a[lg][-1]
    else:
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        if(a_count[lg]>=2):
            left1 = a[lg][-1]
            left2 = a[lg][-2]
        else:
            left1 = a[lg][-1]
            while(True):
                lg -=1
                if(a_count[lg]>0):
                    break
            left2 = a[lg][-1]
    #right
    if(a_count[group]>=j+2):
        right1 = a[group][j]
        right2 = a[group][j+1]
    elif(a_count[group]>=j+1):
        right1 = a[group][j]
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        right2 = a[rg][0]
    else:
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        if(a_count[rg]>=2):
            right1 = a[rg][0]
            right2 = a[rg][1]
        else:
            right1 = a[rg][0]
            while(True):
                rg += 1
                if(a_count[rg]>0):
                    break
            right2 = a[rg][0]

    ans += ((right2 - right1)* (i - left1) + (right1 - i)* (left1 - left2)) * val
    a[group].insert(j,i)
    a_count[group] += 1

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

#!/usr/bin/env pypy3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

import sys
N,M=map(int,input().split())
ab=[]
for i in range(M):
  ab+=[list(map(int,input().split()))]
come=[]
go=[]
for i in range(M):
  if ab[i][0]==1:
    if ab[i][1] in come:
      print("POSSIBLE")
      sys.exit()
    come+=[ab[i][1]]
  if ab[i][1]==N:
    if ab[i][0] in come:
      print("POSSIBLE")
      sys.exit()
    come+=[ab[i][0]]
 
print("IMPOSSIBLE")

### FIXED CODE ###

import sys
N,M=map(int,input().split())
come=[0]*N
for i in range(M):
  ab=list(map(int,input().split()))
  if ab[0]==1:
    if come[ab[1]]:
      print("POSSIBLE")
      sys.exit()
    come[ab[1]]=1
  if ab[1]==N:
    if come[ab[0]]:
      print("POSSIBLE")
      sys.exit()
    come[ab[0]]=1
 
print("IMPOSSIBLE")
### BUGGY CODE ###

import itertools
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


D, G = list(map(int, sys.stdin.buffer.readline().split()))
P, C = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(D)]))
P = np.array(P, dtype=int)
C = np.array(C, dtype=int)

scores = P * np.arange(1, D + 1, dtype=int) * 100 + C
ans = INF
for order in itertools.permutations(range(D)):
    ps = scores[list(order)].cumsum()
    counts = P[list(order)].cumsum()
    i = np.searchsorted(ps, G)
    if i == 0:
        a = math.ceil(G / (order[0] * 100 + 100))
        ans = min(ans, a, P[order[0]])
    else:
        a = counts[i - 1]
        score = ps[i - 1]
        a += min(math.ceil((G - score) / (order[i] *100 + 100)), P[order[i]])
        ans = min(ans, a)
    # print(order, ans)
print(ans)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

D, G = list(map(int, sys.stdin.readline().split()))
P, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(D)]))

P = np.array(P, dtype=int)
C = np.array(C, dtype=int)
A = np.arange(1, D + 1, dtype=int) * 100  # 1問のスコア
comp_scores = P * A + C

ans = P.sum()
for i in range(D):
    # i: 途中まで解く
    # comp: True ならその問題は全部解く
    for comp in itertools.product([True, False], repeat=D):
        comp = np.array(comp)
        comp[i] = False
        cnt = P[comp].sum()
        score = comp_scores[comp].sum()
        add_cnt = max(0, min(P[i] - 1, math.ceil((G - score) / A[i])))
        add_score = A[i] * add_cnt
        if score + add_score >= G:
            ans = min(ans, cnt + add_cnt)
print(ans)
### BUGGY CODE ###

N = int(input())
for n in range(1, N+1):
    ans = 0
    for x in range(1, int(n**0.5)+1):
        for y in range(1, int(n**0.5)+1):
            for z in range(1, int(n**0.5)+1):
                v = x**2+y**2+z**2+x*y+y*z+z*x
                if v>n:
                    continue
                elif v==n:
                    ans += 1
    print(ans)

### FIXED CODE ###

def solve():
    N = int(input())
    f = lambda x,y,z:x*x+y*y+z*z+x*y+y*z+z*x
    MAX = 10000

    ans = [0]*(MAX+1)
    for x in range(1, 101):
        if f(x,0,0)>MAX:
            break
        for y in range(1, 101):
            if f(x,y,0)>MAX:
                break
            for z in range(1, 101):
                if f(x,y,z)>MAX:
                    break
                ans[f(x,y,z)]+=1
    for i in range(1, N+1):
        print(ans[i])

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

from collections import deque
import copy
H, W = map(int,input().split())

A = [[s == "#" for s in input()] for _ in range(H)]
Q = deque([(y, x) for y in range(H) for x in range(W) if A[y][x]])

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.popleft()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = copy.copy(NQ)
    else:
        break

print(ans-1)

### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

import collections
import math
import copy

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

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
start=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            start.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

for ss in start:
    queue=collections.deque([[ss[0],ss[1]]])
    while len(queue)>0:
        now=queue.popleft()
        for i in range(4):
            ny=now[0]+moves[i][0]
            nx=now[1]+moves[i][1]
            if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.':
                if d[ny][nx]==-1:
                    d[ny][nx]=d[now[0]][now[1]]+1
                    queue.append([ny,nx])
                elif d[ny][nx]>d[now[0]][now[1]]+1:
                    d[ny][nx]=d[now[0]][now[1]]+1
                    queue.append([ny,nx])
nax=0
for i in range(H):
    for j in range(W):
        nax=max(nax,d[i][j])
print(nax)

### FIXED CODE ###

import collections
import math
import copy

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

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            nax=max(nax,d[ny][nx])
            queue.append([ny,nx])


print(nax)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    t = sum(v) + 1
    l = [float('inf')] * (t + 1) 
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            if j == v[i]:
                l[j] = min(l[j], w[i])
            elif l[j - v[i]] + w[i] < l[j]:
                l[j] = l[j - v[i]] + w[i]
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    t = sum(v)
    l = [m + 1] * (t + 1)
    l[0] = 0
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            k = l[j - v[i]] + w[i]
            if k < l[j]:
                l[j] = k
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()
### BUGGY CODE ###

h,n=map(int,input().split())
AB=[]
for _ in range(n):
    AB.append(list(map(int,input().split())))
dp=[0]+[float("INF")]*h
for i in range(1,h+1):
    for a,b in AB:
        if i<=a:
            dp[i]=min(dp[i],b)
        else:
            dp[i]=min(dp[i],b+dp[i-a])
print(dp[-1])

### FIXED CODE ###

h,n=map(int,input().split())
AB=[]
for _ in range(n):
    AB.append(list(map(int,input().split())))
dp=[0]+[float("INF")]*h
for i in range(1,h+1):
    for a,b in AB:
        if i<=a:
            dp[i]=min(dp[i],b)
        else:
            dp[i]=min(dp[i],b+dp[i-a])
print(dp[-1])
### BUGGY CODE ###

import collections
s = input()
dp = [0 for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    k = len(s) - i
    dp[i] = (dp[i-1] + int(s[k])*(pow(10,i-1)))%2019

count_d = collections.defaultdict(int)
for mod in dp:
    count_d[mod] += 1

cnt = 0
for v in count_d.values():
    if v >= 2:
        cnt += v*(v-1)//2
print(cnt)

### FIXED CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
d = {}
# まず全体における答えを求める
for i in A:
    if i in d.keys():
        d[i] += 1
    else:
        d[i] = 1
whole_ans = sum(map(lambda x: x*(x-1)//2, d.values()))
# 差分更新
for i in A:
    d_ = d.copy()
    d_[i] -= 1
    dif = (d_[i]*(d_[i]-1) - d[i]*(d[i]-1)) // 2
    part_ans = whole_ans + dif
    print(part_ans)

### FIXED CODE ###

N = int(input())
A = list(map(lambda x: int(x)-1, input().split()))
d = [0] * N
for i in A:
    d[i] += 1
s = sum(map(lambda x: x*(x-1)//2, d))
for i in A:
    print(s + (1 - d[i]))
### BUGGY CODE ###

import sys

values = [int(input()) for i in range(int(input()))]

maxv = - sys.maxsize - 1

for c, i in enumerate(values):
    for j in values[c + 1:]:
        maxv = max(maxv, j - i)

print(maxv)



### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)