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

from decimal import Decimal

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

for i in range(n):
  a[i] = [(-1) * a[i], Decimal(str((-1) * a[i])), (-1) * a[i], Decimal(str((-1) * a[i])), 1]

import heapq
heapq.heapify(a)

for _ in range(k):
  i = heapq.heappop(a)
  i[4] += 1
  i[0] = i[2] // i[4]
  i[1] = i[3] / i[4]
  heapq.heappush(a, i)

print((-1) * heapq.heappop(a)[0])

### FIXED CODE ###

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

# binary search
left = 1
right = 10 ** 9

while left < right:
    center = (left + right) // 2

    total = 0
    for i in a:
        if i % center == 0:
            i -= 1
        total += i//center
    
    if total > k:
        left = center + 1
    else:
        right = center

print(left)
### BUGGY CODE ###

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

res = 0

for i in range(N-2):
    L1 = L[i+1:]
    a = L[i]
    for j in range(len(L1)-1):
        L2 = L1[j+1:]
        b = L1[j]
        temp1 = max(L2)
        temp2 = min(L2)
        if temp2 >= a + b:
            break
        elif temp1 <= a - b:
            break
        elif temp1 <= b - a:
            break
        LS2 = list(set(L2))
        M2 = len(LS2)
        for k in range(M2):
            c = LS2[k]
            sum = a + b + c
            if (sum > 2*a) & (sum > 2*b) & (sum > 2*c):
                res += L2.count(c)

print(res)


### FIXED CODE ###

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

v = L[:]
v.sort()

res = 0

import bisect

for i in range(N-2):
    a = v[i]
    for j in range(i+1,N-1):
        b = v[j]
        sup = a + b
        #inf = max(a-b,b-a)
        iterS = bisect.bisect_left(v,sup)
        #iterI = bisect.bisect_left(v,inf+1)
        #print(a,b,sup,inf,iterS,iterI)
        res += iterS - (j+1)

print(res)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))



    









### FIXED CODE ###

import collections

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

for i in range(1,N+1):
    print(c[i])
### BUGGY CODE ###

s=input()
q=int(input())
cnt1=0
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s="".join([s,query[2]])
        else:
            s="".join([query[2],s])
if cnt1%2==0:
    print(s)
else:
    s2=""
    for i in range(len(s)):
        s2="".join([s2,s[-1-i]])
    print(s2)

### FIXED CODE ###

s=input()
q=int(input())
cnt1=0
s_mae=[]
s_ushiro=[]
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s_ushiro.append(query[2])
        else:
            s_mae.append(query[2])
s1=""
for i in range(len(s_mae)):
    s1=s1+s_mae[-1-i]
s2="".join(s_ushiro)
ans=s1+s+s2
if cnt1%2==0:
    print(ans)
else:
    ans2=""
    for i in range(len(ans)):
        ans2=ans2+ans[-1-i]
    print(ans2)
### BUGGY CODE ###

n = int(input())
s = input()

dp = [[0 for _ in range(n)] for _ in range(n)]
all_patterns = dict()
max_val = 0
for i in range(n):
    for j in range(i,n):
        target = s[i:j+1]
        if target in all_patterns: 
            if len(target) > max_val:
                if i>all_patterns[target][1]:
                    max_val = len(target)
        else:
            all_patterns[target] = [i,j]

print(max_val)

### FIXED CODE ###

n = int(input())
s = input()

def z_algorithm(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A


length = n

ans = 0
for i in range(length):
    temp = z_algorithm(s[i:])
    for j in range(len(temp)):
        if min(temp[j],j) > ans:
            ans = min(temp[j],j)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

m = a[0]
for i in a[1:]:
    m *= i

if m > pow(10, 18):
    print("-1")
else:
    print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print("0")
    exit()

m = a[0]
over = False
limit = pow(10, 18)
for i in a[1:]:
    m *= i
    if m > limit:
        over = True
        break

if over:
    print("-1")
else:
    print(m)
### BUGGY CODE ###

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

for i in range(n):
	ts = input()
	ad = True

	for j in s:
		if ts == j:
			ad = False

	if ad :
		s.append(ts)


print(len(s))





### FIXED CODE ###

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

for i in range(n):
	s.append(input())

ss = sorted(s)
c = len(s)

for i in range(1,n):
	if ss[i-1] == ss[i]:
		c -= 1

print(c)
### BUGGY CODE ###

#from scipy.special import comb
#from math import factorial
import collections
from operator import mul
from functools import reduce

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#a = cmb(n,r)
c = collections.Counter(A)
l1 = []
l2 = []
l3 = []
for i in c.keys():
  l1.append(i)
  if c[i] == 1:
    l2.append(0)
    l3.append(0)
  if c[i] == 2:
    l2.append(1)
    l3.append(0)
  if c[i] >= 3:
    l2.append(cmb(c[i], 2))
    l3.append(cmb(c[i]-1, 2))    

l4 = []
for i in c.keys():
  sum = 0
  for j in c.keys():
    var_index = l1.index(j)
    if i == j:
      sum += l3[var_index]
    else:
      sum += l2[var_index]
  l4.append(sum)
#print(l4)
for i in range(N):
  var_index = l1.index(A[i])
  print(l4[var_index])

### FIXED CODE ###

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

from collections import Counter
C=Counter(A)
ANS=0
for i in C.values():
    ANS+=i*(i-1)//2

for a in A:
    k=C[a]

    print(ANS-(k*(k-1)//2)+((k-1)*(k-2)//2))
### BUGGY CODE ###

n = int(input())
h = list(int(i) for i in input().split())
count = 0
while not all(i==0 for i in h):
    if 0 in h:
        zero_index = [i for i,x in enumerate(h) if x==0]
        for i in range(len(zero_index)):
            if i==0:
                if not all(h[j]==0 for j in range(zero_index[i])):
                    for j in range(zero_index[i]):
                        h[j] -= 1
                    count += 1
            elif i==len(zero_index)-1 and not zero_index[i]==n-1:
                if not all(h[j]==0 for j in range(zero_index[i]+1,n)):
                    for j in range(zero_index[i]+1,n):
                        h[j] -= 1
                    count += 1
            else:
                if not all(h[j]==0 for j in range(zero_index[i-1]+1,zero_index[i])):
                    for j in range(zero_index[i-1]+1, zero_index[i]):
                        h[j] -= 1
                    count += 1
    else:
        for i in range(n):
            h[i] -=1
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
h = list(int(i) for i in input().split())
count = 0
while not all(height==0 for height in h):
    index = [i for i,x in enumerate(h) if not x==0]
    for i in range(len(index)):
        h[index[i]] -= 1
        if not i==0:
            if index[i]-index[i-1]>1:
                count += 1
    count += 1
print(count)
### BUGGY CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N) + 1)
    for i in range(1, M):
        if P % (i ** N) == 0:
            _max = i

    if P % ((i + 1) ** N) == 0:
        _max = (i + 1)

    print(_max)

### FIXED CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N) + 1.0 * 1e-9)
    for i in range(1, M + 1):
        if P % (i ** N) == 0:
            _max = i

    print(_max)
### BUGGY CODE ###

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


for i in range(min(K, 42)):
    cum_sum = [0]*N
    for j in range(N):
        left = max(0, j - A[j])
        right = min(N-1, j+A[j])
        cum_sum[left] += 1
        if right + 1 < N:
            cum_sum[right+1] -= 1
    A[0] = cum_sum[0]
    for j in range(N-1):
        cum_sum[j+1] += cum_sum[j]
        A[j+1] = cum_sum[j+1]
    
        
for i in range(N):
    print(A[i], " ", end = "")
print()

### FIXED CODE ###

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


for i in range(min(K, 42)):
    cum_sum = [0]*N
    for j in range(N):
        left = max(0, j - A[j])
        right = min(N-1, j+A[j])
        cum_sum[left] += 1
        if right + 1 < N:
            cum_sum[right+1] -= 1
    A[0] = cum_sum[0]
    for j in range(N-1):
        cum_sum[j+1] += cum_sum[j]
        A[j+1] = cum_sum[j+1]
    
        
for i in range(N):
    print(A[i], " ", end = "")
print()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
#    print('{:06}{:06}'.format(ken,bisect.bisect_right(ken_year_map[ken], year)))
    print('{:06}{:06}'.format(ken,ken_year_map[ken].index(year)+1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print('{:06}{:06}'.format(ken,bisect.bisect_right(ken_year_map[ken], year)))
### BUGGY CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(n+1)] # dp[i][j]:i番目までで j mod 13.
dp[0][0]=1
for i in range(1,n+1):
  for j in range(13):
    if s[i-1]=='?':
      for k in range(10):
        dp[i][(j*10+k)%13]+=dp[i-1][j]
        dp[i][(j*10+k)%13]%=mod
    else:
      dp[i][(j*10+int(s[i-1]))%13]+=dp[i-1][j]
      dp[i][(j*10+int(s[i-1]))%13]%=mod
print(dp[n][5])

### FIXED CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(n+1)] # dp[i][j]:i番目までで j mod 13.
dp[0][0]=1
for i in range(1,n+1):
  for j in range(13):
    if s[i-1]=='?':
      for k in range(10):
        dp[i][(j*10+k)%13]+=dp[i-1][j]
        dp[i][(j*10+k)%13]%=mod
    else:
      dp[i][(j*10+int(s[i-1]))%13]+=dp[i-1][j]
      dp[i][(j*10+int(s[i-1]))%13]%=mod
print(dp[n][5])
### BUGGY CODE ###

N,M = (int(x) for x in input().split())
a = list(map(int,input().split()))

a.sort()

l = len(a) - 1
t = l
for i in range(M):
  t = l
  a[l] = a[l] // 2
  while a[t-1] > a[t]:
    tmp = a[t]
    a[t] = a[t-1]
    a[t-1] = tmp
    t -= 1
    if t==0:
      break;
print(sum(a))
    


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

n,t=map(int,input().split())
a=input().split()
for i in range(n):
    a[i]=int(a[i])

saisyo=min(a)
saidai=0
count=0

for i in range(n-1):
    x=a.pop()
    if x==saisyo:
        saisyo=min(a)
    elif x-saisyo>=saidai:
        mouke=x-saisyo
        if mouke>saidai:
            saidai=mouke
            count=1
        elif mouke==saidai:
            count+=1
    
print(count)

### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
saisyo=a[0]
saidai=0
count=0
for i in range(n):
    if a[i]<saisyo:saisyo=a[i]
    else:
        if a[i]-saisyo>saidai:
            saidai=a[i]-saisyo
            count=1
        elif a[i]-saisyo==saidai:
            count+=1
print(count)
### BUGGY CODE ###


# 入力部
N, K = map(int, input().split())
data_list = []
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    data_list.append([x, y, c])

# スコア行列[K, K]
# 白チェッカー左下を(x, y)としたときの正解数-誤答数
score_matrix = [[0 for x in range(K)] for y in range(K)]

# 座標をmod Kに変換してスコア行列[K, K]を導出 O(N)
# 同時に初期値であるhope[0][0]も計算
score_matrix = [[0 for x in range(K)] for y in range(K)]
# 白チェッカー左下が(0, 0)のときの希望の数
base_hope = 0
for data in data_list:
    x, y, c = data[0] // K, data[1] // K, data[2]
    x_coord, y_coord = data[0] % K, data[1] % K
    # 正解
    if ((x + y) % 2 == 0 and c == "W") or ((x + y) % 2 == 1 and c == "B"):
        score_matrix[y_coord][x_coord] += 1
        base_hope += 1
    # 誤答
    else:
        score_matrix[y_coord][x_coord] -= 1
# print(score_matrix)

# スコア行列の二次元累積和を求める O(K^2)
for y in range(K):
    for x in range(K):
        accum = score_matrix[y][x]
        if x > 0:
            accum += score_matrix[y][x-1]
        if y > 0:
            accum += score_matrix[y-1][x]
        if x > 0 and y > 0:
            accum -= score_matrix[y-1][x-1]
        score_matrix[y][x] = accum
# print(score_matrix)

# 希望行列を累積和に基づき計算していく O(K^2)
# 同時に最大値を計算
max_hope = 0
for y in range(K):
    for x in range(K):
        diff = 0
        if x > 0:
            diff += score_matrix[K-1][x-1]
        if y > 0:
            diff += score_matrix[y-1][K-1]
        if x > 0 and y > 0:
            diff -= 2 * score_matrix[y-1][x-1]
        hope = base_hope - diff
        true_hope = max(hope, N - hope)
        if true_hope > max_hope:
            max_hope = true_hope

print(max_hope)

### FIXED CODE ###

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

score = [[0] * (K+1) for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = hope if hope > N - hope else N - hope
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)
### BUGGY CODE ###

class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)  # 末尾に追加する

    def dequeue(self):
        return self.data.pop(0)  # 先頭を取り出す

    def is_Empty(self):  # 空であればTrueを返す
        if len(self.data) == 0:
            return True
        else:
            return False


N, Q = map(int, input().split())  # N個の頂点, Q回の操作

# 辺を受け取る
graph = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)

count = [0] * N
# その頂点に対して与えられるカウントは伝播する
for i in range(Q):  # Q個の操作について
    p, x = map(int, input().split())
    # ある頂点を根とする部分木には、今現在のcountが全て伝播していく
    count[p-1] += x

q = Queue()
q.enqueue(0)  # 開始のノード
flag = [False] * N

while not q.is_Empty():
    v = q.dequeue()
    flag[v] = True  # 部分木の根を到達済みにする

    for e in graph[v]:  # vを根にもつノード全てに操作をする
        # graphは子のみを格納するのではなく、そのノードから出ている辺を
        # 親とか子供とか関係なく全て格納してしまうため、親の方向に
        # 対して伝播をしないようにflagで管理する
        if flag[e]:  # 頂点eがvの親であればスルー
            continue
        # eはvの子供であることが確定する
        count[e] += count[v]  # 親の値を伝播させていく
        q.enqueue(e)

print(*count)


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  S = tuple(input().rstrip() for _ in range(h))
  L = [[0]*w for _ in range(h)]
  R = [[0]*w for _ in range(h)]
  U = [[0]*w for _ in range(h)]
  D = [[0]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if j > 0:
        if S[i][j-1] == ".":
          L[i][j] = L[i][j-1]+1
        if S[i][w-j] == ".":
          R[i][w-1-j] = R[i][w-j]+1
      if i > 0:
        if S[i-1][j] == ".":
          U[i][j] = U[i-1][j]+1
        if S[h-i][j] == ".":
          D[h-1-i][j] = D[h-i][j]+1
  ans = 0
  for i in range(h):
    for j in range(w):
      if S[i][j] == ".":
        temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
        ans = max(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

MOD = 10**9+7
h, w = map(int, input().split())
S = [input() for _ in range(h)]
L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if j > 0:
      if S[i][j-1] == ".":
        L[i][j] = L[i][j-1]+1
      if S[i][w-j] == ".":
        R[i][w-1-j] = R[i][w-j]+1
    if i > 0:
      if S[i-1][j] == ".":
        U[i][j] = U[i-1][j]+1
      if S[h-i][j] == ".":
        D[h-1-i][j] = D[h-i][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == ".":
      temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
      ans = max(ans, temp)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

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

#!/usr/bin/env python3
import os


def main():
    inp = os.read(0, os.fstat(0).st_size).split()
    n = int(inp[0])
    m = int(inp[1])

    wi = int(inp[2])
    vi = int(inp[3])

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = int(inp[2 * i + 4])
        vi = int(inp[2 * i + 5])
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-1])