Harryxun/stf_run huggingface dataset:
import bisect
from collections import deque
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0)<K:
    print(0)
    exit()
A=A[::-1]
x=deque(A[bisect.bisect_right(A,0):][::-1]+[0])
y=deque(A[:bisect.bisect_left(A,0)]+[0])
c=0
t=[]
while c<K:
    if c==K-1 or len(y)<2:
        t.append(x.popleft())
        c+=1
    elif not x:
        t.append(y.popleft())
        t.append(y.popleft())
        c+=2
    elif x[0]*x[1]>=y[0]*y[1]:
        t.append(x.popleft())
        c+=1
    else:
        t.append(y.popleft())
        t.append(y.popleft())
        c+=2
ans=1
for i in t:
    ans*=i
    ans%=MOD
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K==1:
    print(A[0]%MOD)
    exit()
if K%2==1 and A[0]==0:
    print(0)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0) <K:
    print(0)
    exit()
if A[-1]>=0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
l=0
r=N-1
t=[]
c=0
if K%2==1:
    tk=K-1
    flg=True
else:
    tk=K
    flg=False
while c<tk:
    if A[l]*A[l+1]<=A[r]*A[r-1]:
        t.append(A[r])
        t.append(A[r-1])
        r-=2
        c+=2
    else:
        t.append(A[l])
        t.append(A[l+1])
        l+=2
        c+=2
if flg:
    t.append(A[l])
ans=1
for i in t:
    ans=ans*i%MOD
print(ans)
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
re = 0
re2 = 0

for i in range(n):
    for m in range(n-i-1):
        re = a[i]*a[i+m+1]
        re2 += re

ans = re2 %1000000007
print(ans)

### FIXED CODE ###

d,t,s =map(int,input().split())
if d/s <=t :
    print('Yes')
else :
    print('No')
# E Knapsack 2

import sys

sys.setrecursionlimit(10**8)

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
dp[0][0] = 0
memo = [[False] * (MAX_V) for _ in range(n+1)]
memo[0] = [True] * (MAX_V)

def dp_solve(i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_v < 0:
        _ret = dp_solve(i-1, j)
    else:
        _ret = min(dp_solve(i-1, j), dp_solve(i-1, j-_v) + _w)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(n, w))

### FIXED CODE ###

# E Knapsack 2

from collections import deque

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(MAX_V):
        if j-_v < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-_v]+_w)

ans = 0
for i in range(MAX_V):
    if dp[n][i] <= w:
        ans = i
print(ans)
N = int(input())
info = [[] for _ in range(N)]
people = [-1] * N
for i in range(N):
    A = int(input())
    for j in range(A):
        x , y = map(int,input().split())
        info[i].append([A , x - 1 , y])
#print(info[0][0][0])
ans = 0
for i in range(2 ** N):
    cnt = 0
    Flag = True
    for j in range(N):
        if i >> j & 1:
            cnt += 1
            people[j] = 1
        else:
            people[j] = 0
    for j in range(N):
        if i >> j & 1:
            info_num = info[j][0][0]
            for k in range(info_num):
                judge = info[j][k][2]
                origin = people[info[j][k][1]]
                if judge != origin:
                    Flag = False
                    break
        if not Flag:
            break
    if Flag:
        if ans < cnt:
            ans = cnt
print(ans)


### FIXED CODE ###

N = int(input())
info = [[] for _ in range(N)]
people = [-1] * N
for i in range(N):
    A = int(input())
    if A == 0:
        info[i].append([0])
    for j in range(A):
        x , y = map(int,input().split())
        info[i].append([A , x - 1 , y])
#print(info[0][0][0])
ans = 0
# ビット全探索を行う
for i in range(2 ** N):
    cnt = 0
    Flag = True
    # ビットが１の時、正直者としてpeopleに格納
    for j in range(N):
        if i >> j & 1:
            cnt += 1
            people[j] = 1
        else:
            people[j] = 0
    for j in range(N):
        # 正直者の発言と実際に正直者であるかを判定
        if i >> j & 1:
            info_num = info[j][0][0]
            for k in range(info_num):
                judge = info[j][k][2]
                origin = people[info[j][k][1]]
                if judge != origin:
                    Flag = False
                    break
        if not Flag:
            break
    if Flag:
        if ans < cnt:
            ans = cnt
print(ans)
N,R = map(int,input().split())
print(R if N >= 10 else R+{100*(10-N)})


### FIXED CODE ###

N,R = map(int,input().split())

print(R if N >= 10 else R + 100*(10-N))
import math
A, B, C, D = map(int, input().split())
A = A-1
f=math.gcd(C,D)
f2=C*D//f

Aans = A - (A//C + A//D - A//f2)
Bans = B - (B//C + B//D - B//f2)
print(Bans- Aans)

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
A = A-1
f=fractions.gcd(C,D)
f2=C*D//f

Aans = A - (A//C + A//D - A//f2)
Bans = B - (B//C + B//D - B//f2)
print(Bans- Aans)
import math
a,b,c,d=list(map(int,input().split()))

def lcm(x,y):
    return (x*y)//math.gcd(x,y)

def ans_cnt(i,y,z):
    return i - (i//y + i//z - i//lcm(y,z))

print(ans_cnt(b,c,d)-ans_cnt(a-1,c,d))

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())

def lcm(x,y):
    return (x*y)//gcd(x,y)

def ans_cnt(i,y,z):
    return i - (i//y + i//z - i//lcm(y,z))

print(ans_cnt(b,c,d)-ans_cnt(a-1,c,d))
N,A,B = map(int.input())
if ((N+A+B)%2==1):
    print("Borys")
else:
    print("alice")

### FIXED CODE ###

n, a, b = map(int,input().split())
m = a + b
if (m % 2==1):
    print("Borys")
else:
    print("Alice")
d=str(input())
if(d="SAT"):
   print(1)
elif(d="FRI"):
  print(2)
elif(d="THU"):
  print(3)
elif(d="WED"):
  print(4)
elif(d="TUE"):
  print(5)
elif(d="MON"):
  print(6)
else:
  print(7)

### FIXED CODE ###

d=input()
if(d=="SAT"):
  print(1)
elif(d=="FRI"):
  print(2)
elif(d=="THU"):
  print(3)
elif(d=="WED"):
  print(4)
elif(d=="TUE"):
  print(5)
elif(d=="MON"):
  print(6)
else:
  print(7)
N, M = map(int, input().split())
x = list(map(int, input().split()))

x.sort()
s = [0] * (M - 1)
for i in range(M - 1):
    s[i] = x[i + 1] - x[i]

s.sort(reverse=True)
res = sum(s)
for i in range(N - 1):
    res -= s[i]
print(res)

### FIXED CODE ###

N, M = map(int, input().split())
x = list(map(int, input().split()))
if N >= M:
    print(0)
    quit()


x.sort()
s = [0] * (M - 1)
for i in range(M - 1):
    s[i] = x[i + 1] - x[i]

s.sort(reverse=True)

res = sum(s)
if M == 1:
    print(0)
    quit()
else:
    for i in range(N - 1):
        res -= s[i]

print(res)
from sys import stdin
read = stdin.read
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MAX_A = 300000

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    N, K = i_map()
    A = list(map(int, read().strip().splitlines()))
    s = SegTree([0]*N, lambda x, y : max(x,y), 0)
    ans = 0
    for a in A:
        l, r = max(a - K, 0), min(a + K + 1, MAX_A)
        now = s.query(l, r) + 1
        s.update(a, now)
        ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin
read = stdin.read
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MAX_A = 300005

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    N, K = i_map()
    A = list(map(int, read().strip().splitlines()))
    s = SegTree([0]*MAX_A, lambda x, y : max(x,y), 0)
    ans = 0
    for a in A:
        l, r = max(a - K, 0), min(a + K + 1, MAX_A)
        now = s.query(l, r) + 1
        s.update(a, now)
        ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()
from collections import defaultdict as dd
from collections import deque
import collections as col
d=dd(list)
q=deque([])

N,M=map(int, input().split())
for _ in range(M):
    f=0
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)
chk=[0]*N
chk[0]=1
temp=1
a=0
while a<N:
    for i in range(len(d[temp])):
        chk[d[temp][i]-1]=1
        q.append(d[temp][i])

    if len(q)>0:
        while a<N:
            if chk[a]==0:
                chk[a]=1
                temp=a+1
                break
            a+=1
    else:
        temp=q.pop()

ans=0
for i in  range(N):
    ans=max(ans,len(col.Counter(d[i]))+1)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

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

par=(list(range(N+1)))
rank=[1]*(N+1)

for _ in range(M):
    A,B=map(int, input().split())
    union(A,B)

print(max(rank))
x, y, z = map(int, input().split())

print(' '.join(z, x, y))

### FIXED CODE ###

x, y, z = map(str, input().split())

print(" ".join([z, x, y]))
m,n=map(int,input().split())
x=[]
for i in range(m):
  a=list(map(int,input().split()))
  x.append(a)
y=[]
for i in range(m):
  z=[0,0,0,0,0,0,0,0]
  z[0]=x[i][0]+x[i][1]+x[i][2]
  z[1]=x[i][0]+x[i][1]-x[i][2]
  z[2]=x[i][0]-x[i][1]+x[i][2]
  z[3]=x[i][0]-x[i][1]-x[i][2]
  z[4]=-x[i][0]+x[i][1]+x[i][2]
  z[5]=-x[i][0]+x[i][1]-x[i][2]
  z[6]=-x[i][0]-x[i][1]+x[i][2]
  z[7]=-x[i][0]-x[i][1]-x[i][2]
  y.append(z)
sort(y,axis=0)
z=[0,0,0,0,0,0,0,0]
for i in range(m-1,m-n-1):
  z+=y[i]
sort(z)
print(z[7])
  

### FIXED CODE ###

import numpy as np
m,n=map(int,input().split())
x=[]
for i in range(m):
  a=list(map(int,input().split()))
  x.append(a)
y=[]
for i in range(m):
  z=[0,0,0,0,0,0,0,0]
  z[0]=x[i][0]+x[i][1]+x[i][2]
  z[1]=x[i][0]+x[i][1]-x[i][2]
  z[2]=x[i][0]-x[i][1]+x[i][2]
  z[3]=x[i][0]-x[i][1]-x[i][2]
  z[4]=-x[i][0]+x[i][1]+x[i][2]
  z[5]=-x[i][0]+x[i][1]-x[i][2]
  z[6]=-x[i][0]-x[i][1]+x[i][2]
  z[7]=-x[i][0]-x[i][1]-x[i][2]
  y.append(z)
p=np.array(y)
sidx = p.argsort(axis=0)
p=p[sidx, np.arange(sidx.shape[1])]
z=[0,0,0,0,0,0,0,0]
for i in range(m-1,m-n-1,-1):
  for j in range(8):
  	z[j]+=p[i][j]
print(max(z))
r = int(input())
circle_squre = r * r * 3.141592
circle_length = (r*2) * 3.141592

print('{:.5f}'.format(circle_squre),'{:.5f}'.format(circle_length))

### FIXED CODE ###

from math import pi
r = float(input())
circle_squre = r * r * pi
circle_length = (r*2) * pi

print('{}'.format(circle_squre),'{}'.format(circle_length))
for i in range(N) :
  b=input().split()
  w=int(b[0])
  v=int(b[1])

  wv_list.append([w,v])

n_list=  [[0 for i in range(W+1)] for j in range(N)]


if wv_list[0][0]<=W :
    n_list[0][wv_list[0][0]]=wv_list[0][1]

for i in range(1,N) :
    for j in range(W) :
        s=j+wv_list[i][0]
        if s<=W :
            n_list[i][s]=max(n_list[i-1][j]+wv_list[i][1],n_list[i][s])

        n_list[i][j] = max(n_list[i - 1][j],n_list[i][j])

print(max(n_list[-1]))

### FIXED CODE ###

a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]

#最初のアイテムに関して、重みを適切な価値のところにいれている
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):
  # 今まで全く選んでなかった場合に、i番目のアイテムを選んだ時
  n_list[i][wv_list[i][1]] = wv_list[i][0]
  for j in range(max_value):

    s = j + wv_list[i][1]
    #アイテムを選んだらこうなりますよってのを更新
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])

    #選ばんかったらこうなりますよってのを更新？
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
  
for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break
n=int(input())
lst=[[[0]*10 for i in range(0,3)] for j in range(0,4)]
for k in range(n):
    b,f,r,v = map(int,input().split())
    lst[b-1][f-1][r-1] +=v
x=0
for i in range (4)
    if x!=0: print("#"*20)
    +=x
    for a in range(3):
        for b in range(10):
            print((lst[i][a][b]),end="")
        print()


### FIXED CODE ###

n= int(input())
tbl=[[[0]*10 for i in range(0,3)] for j in range(0,4)]
for k in range(n):
    b,f,r,v = map(int,input().split())
    tbl[b-1][f-1][r-1] +=v
x=0
for i in range (4):
    if x !=0 : print("#"*20)
    x +=1
    for a in range(3):
        for b in range(10):
            print(" %d"%(tbl[i][a][b]),end="")     
        print()
b.insert(0,a[i])


### FIXED CODE ###

from collections import deque
n=int(input())
a=deque([int(i) for i in input().split()])
b=deque()

if n%2==0:
    for i in range(n):
        if i % 2 == 0:
            b.append(a.popleft())
        else:
            b.appendleft(a.popleft())
else:
    for i in range(n):
        if i % 2 == 0:
            b.appendleft(a.popleft())
        else:
            b.append(a.popleft())
print(*b)
N=int(input())
S=str(input())

for i in range(len(S)-1):
    if S[i]==S[i+1]:
        idx=i        
idx=idx+1
sub_X=S[:idx]
sub_Y=S[idx:]
count=0
for str1 in sub_X:
    for str2 in sub_Y:
        if str1==str2:
            count+=1
            
print(int(count/2))

### FIXED CODE ###

N=int(input())
S=list(input())
a=[]

for i in range(1,N):
    x=set(S[:i-1:])
    y=set(S[i-1::])
    a.append(len(list(x&y)))
    
print(max(a))
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


def make_p():
    P = []
    m = 55555 + 1
    mask = [0] * m

    for i in range(2, m):
        # print(i)
        if mask[i] == 0:
            for j in range(m):
                if i * j >= m:
                    break
                mask[i * j] = 1
            P.append(i)

    return P


@mt
def slv(N):
    p = [
        2, 10781, 10853, 10313, 10937, 9587, 10499, 10487, 10399, 9479, 9343,
        10607, 10631, 10477, 9973, 10559, 10093, 10691, 11093, 10079, 10613,
        10177, 10733, 10831, 10903, 10993, 10331, 10369, 10799, 10651, 11071,
        10567, 10883, 10627, 10453, 10193, 10837, 9533, 10091, 10711, 9851,
        11083, 10433, 9941, 10321, 11059, 10529, 10303, 10357, 10391, 11003,
        10531, 10103, 10889, 10753
    ]

    return ' '.join(str, p[:N])


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N):
    ans = []
    ps = []
    n = 1
    while True:
        n += 2
        for p in ps:
            if n % p == 0:
                break
        else:
            ps.append(n)
            if n % 5 == 1:
                ans.append(n)
                if len(ans) >= N:
                    return ' '.join(map(str, ans))


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()
a = r*r
print(a)

### FIXED CODE ###

r = int(input())
print(r*r)
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

a,b,c,x,y = I()
p = []
for i in range(10**5+1):
    cash = 2*c*i+a*max(0,x-i)+b*max(0,y-i)
    c.append(cash)

print(min(p))


### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

a,b,c,x,y = I()
p = []
for i in range(10**5+1):
    cash = 2*c*i+a*max(0,x-i)+b*max(0,y-i)
    p.append(cash)

print(min(p))
g = [0,2,0,1,0,1,0,0,1,0,1,0]
x, y = map(int, input().split())
print('Yes' if g[x]==g[y] else 'No')

### FIXED CODE ###

g = [-1,0,2,0,1,0,1,0,0,1,0,1,0]
x, y = map(int, input().split())
print('Yes' if g[x]==g[y] else 'No')
from itertools import combinations_with_replacement

n, m, q = map(int,input().split())
l = []
s = []
for _ in range(q):
    a, b, c, d = map(int,input().split())
    l.append([a, b, c, d])

ps = list(combinations_with_replacement(range(2, m+1), n-1))
n_p = len(ps)

for i in range(n_p):
    ns = [1] + list(ps[i])
    ss = 0
    for j in range(q):
        k = l[j]
        if ns[k[1]-1] - ns[k[0]-1] == k[2]:
            ss += k[3]
    s.append(ss)

print(max(s))


### FIXED CODE ###

from itertools import combinations_with_replacement

n, m, q = map(int,input().split())
l = []
s = []
for _ in range(q):
    a, b, c, d = map(int,input().split())
    l.append([a, b, c, d])

ps = list(combinations_with_replacement(range(1, m+1), n-1))
n_p = len(ps)

for i in range(n_p):
    ns = [1] + list(ps[i])
    ss = 0
    for j in range(q):
        k = l[j]
        if ns[k[1]-1] - ns[k[0]-1] == k[2]:
            ss += k[3]
    s.append(ss)

print(max(s))
i=input()
l=int(i[-1])

if l==3:
  print(bon)
elif l==0 or l==1 or l==6 or l==8:
  print(pon)
else:
  print(hon)

### FIXED CODE ###

i=input()
l=int(i[-1])

if l==3:
  print('bon')
elif l==0 or l==1 or l==6 or l==8:
  print('pon')
else:
  print('hon')
#入力処理
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kingaku=[]
for i in range(M):
    x_input, y_input, c_input = map(int, input().split())
    kingaku.append(a[x_input-1][y_input-1]+b[x_input-1][y_input-1]+c_input)
kingaku.append(min(a)+min(b))

print(min(kingaku))

### FIXED CODE ###

#入力処理
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kingaku=[]
for i in range(M):
    x_input, y_input, c_input = map(int, input().split())
    kingaku.append(a[x_input-1]+b[y_input-1]-c_input)
kingaku.append(min(a)+min(b))

print(min(kingaku))
import numpy
def main():


    print(13)

main()

### FIXED CODE ###

def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=[]
    for i in range(N+1):
        graph.append([])
        for j in range(W+1):
            graph[i].append(0)

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1][j]=graph[i][j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i][rest]+inputset[i][0]
                nonchoosevalue=graph[i][j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1][j]=choosevalue
                else:
                    graph[i+1][j]=nonchoosevalue

    print(graph[N][W])

main()