After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.

This morning, as usual, Petya will come to the market. Petya has n different souvenirs to sell; ith souvenir is characterised by its weight w_{i} and cost c_{i}. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than m, and total cost is maximum possible.

Help Petya to determine maximum possible total cost.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.

Then n lines follow. ith line contains two integers w_{i} and c_{i} (1 ≤ w_{i} ≤ 3, 1 ≤ c_{i} ≤ 10^9) — the weight and the cost of ith souvenir.


-----Output-----

Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.


-----Examples-----
Input
1 1
2 1

Output
0

Input
2 2
1 3
2 2

Output
3

Input
4 3
3 10
2 7
2 8
1 1

Output
10

Difficulty: interview

Starter code:

Solutions:
def main():
    n, m = list(map(int, input().split()))

    cost1 = []
    cost2 = []
    cost3 = []

    for i in range(n):
        w, c = list(map(int, input().split()))
        if w == 1:
            cost1.append(c)
        elif w == 2:
            cost2.append(c)
        else:
            cost3.append(c)

    cost1 = sorted(cost1)[::-1]
    cost2 = sorted(cost2)[::-1]
    cost3 = sorted(cost3)[::-1]
    cost3_prefix = [0]
    for c in cost3:
        cost3_prefix.append(cost3_prefix[-1] + c)


    dp = [(0, 0, 0)] * (m + 1)
    dp[0] = (0, 0, 0)

    for i in range(0, m):
        cost, n1, n2 = dp[i]

        if i + 1 <= m and n1 < len(cost1):
            new_cost = cost + cost1[n1]
            if dp[i + 1][0] < new_cost:
                dp[i + 1] = (new_cost, n1 + 1, n2)
        
        if i + 2 <= m and n2 < len(cost2):
            new_cost = cost + cost2[n2]
            if dp[i + 2][0] < new_cost:
                dp[i + 2] = (new_cost, n1, n2 + 1)

        if n1 == len(cost1) and n2 == len(cost2):
            break


    dp_prefix = [0]
    for x in dp[1:]:
        dp_prefix.append(max(dp_prefix[-1], x[0]))

    ans = 0
    for k in range(len(cost3) + 1):
        l = m - 3 * k
        if l < 0:
            continue

        new_ans = cost3_prefix[k] + dp_prefix[l]
        ans = max(new_ans, ans)

    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
from itertools import accumulate

def solve():
    n, m = map(int, input().split())
    w = [[] for i in range(3)]

    for i in range(n):
        wi, ci = map(int, sys.stdin.readline().split())
        wi -= 1
        w[wi].append(ci)

    for i in range(3):
        w[i].sort(reverse=True)

    dp = [0]*(m + 1)
    used = [[0]*2 for i in range(m + 1)]

    s0 = len(w[0])
    s1 = len(w[1])

    if s0 > 0:
        dp[1] = w[0][0]
        used[1] = [1, 0]

    for i in range(2, m + 1):
        if used[i - 1][0] < s0:
            dp[i] = dp[i - 1] + w[0][used[i - 1][0]]
            used[i] = used[i - 1][:]
            used[i][0] += 1
        else:
            dp[i] = dp[i - 1]
            used[i] = used[i - 1][:]

        if used[i - 2][1] < s1 and dp[i] < dp[i - 2] + w[1][used[i - 2][1]]:
            dp[i] = dp[i - 2] + w[1][used[i - 2][1]]
            used[i] = used[i - 2][:]
            used[i][1] += 1

    pf = [0] + list(accumulate(w[2]))

    ans = max(pf[k] + dp[m - 3*k] for k in range(min(len(pf),m // 3 + 1)))

    print(ans)

def __starting_point():
    solve()
__starting_point()

n, m = list(map(int, input().split()))
a = [[], [], []]
for i in range(n):
    w, c = list(map(int, input().split()))
    a[w-1].append(c)
p = [[0], [0], [0]]
for i in range(3):
    a[i].sort(reverse=True)
    for x in a[i]:
        p[i].append(p[i][-1] + x)
ans = 0
for i in range(min(m//3, len(a[2])) + 1):
    w = m - i * 3
    if len(a[1]) * 2 + len(a[0]) <= w:
        ans = max(ans, p[2][i] + p[1][len(a[1])] + p[0][len(a[0])])
        continue
    if not len(a[0]):
        ans = max(ans, p[2][i] + p[1][min(w//2, len(a[1]))])
        continue
    
    if 2 + 2 == 4:
        x = min(len(a[0]), w)
        y = (w - x) // 2
        ans = max(ans, p[2][i] + p[1][y] + p[0][x])

    lo = max((w - len(a[0]) + 1) // 2 + 1, 1)
    hi = min(len(a[1]), w // 2)
    while lo <= hi:
        mi = (lo + hi) // 2
        if a[1][mi - 1] - (p[0][w-mi*2+2] - p[0][w-mi*2]) > 0:
            lo = mi + 1
        else:
            hi = mi - 1
    ans = max(ans, p[2][i] + p[1][hi] + p[0][w-hi*2])
print(ans)


def souvenier_calc(max_weight, weights, value):
    const = len(weights)
    ans = [-1061109567 for x in range(max_weight+1)]
    node = [(x, y) for x, y in zip(weights, value)]
    node = sorted(node, key=lambda x: x[1]/x[0], reverse=True)
    weights = [x[0] for x in node]
    value = [x[1] for x in node]
    sum = 0
    sol = 0
    ans[0] = 0
    for i in range(const):
        sum += weights[i]
        if sum > max_weight:
            sum = max_weight
        down = max(weights[i], sum-3)
        for weight in range(sum, down-1, -1):
            ans[weight] = max(ans[weight], ans[weight-weights[i]]+value[i])
            sol = max(sol, ans[weight])

    return sol

def __starting_point():
    N, M = list(map(int, input().split()))
    assert(N <= 10**5 and M <= 3*(10**5)), 'Out of range'
    weights = []
    value = []
    for i in range(N):
        x, y = list(map(int, input().split()))
        assert(x >= 1 and x <= 3), 'Out of range'
        assert(y >= 1 and y <= 10**9), 'Out of range'
        weights.append(x)
        value.append(y)
    print(souvenier_calc(M, weights, value))

__starting_point()

n, m = map(int, input().split())
d = [[] for i in range(3)]
res_odd = 0
res_even = 0
for i in range(n):
    t1, t2 = map(int, input().split())
    d[t1 - 1].append(t2)
d[0].sort()
d[2].sort(reverse=True)
c = d[1].copy()
if d[0]:
    i = len(d[0]) - 2
    while i >= 1:
        c.append(d[0][i] + d[0][i - 1])
        i -= 2
    c.sort(reverse=True)
    pref = [0 for i in range(len(c) + 1)]
    pref[0] = 0
    for i in range(1, len(c) + 1):
        pref[i] = pref[i - 1] + c[i - 1]
    p = 0
    for i in range(min(len(d[2]), (m - 1) // 3) + 1):
        if i != 0:
            p += d[2][i - 1]
        res_odd = max(res_odd, d[0][-1] + p + pref[min(max(m - i * 3 - 1, 0) // 2, len(pref) - 1)])
i = len(d[0]) - 1
while i >= 1:
    d[1].append(d[0][i] + d[0][i - 1])
    i -= 2
d[1].sort(reverse=True)
pref = [0 for i in range(len(d[1]) + 1)]
pref[0] = 0
for i in range(1, len(d[1]) + 1):
    pref[i] = pref[i - 1] + d[1][i - 1]
p = 0
for i in range(min(len(d[2]), m // 3) + 1):
    if i != 0:
        p += d[2][i - 1]
    res_even = max(res_even, p + pref[min(max(m - i * 3, 0) // 2, len(pref) - 1)])
print(max(res_odd, res_even))

def f():
    n, m = list(map(int, input().split()))
    l = list(tuple(map(int, input().split())) for _ in range(n))
    l.sort(key=lambda e: (0, 6, 3, 2)[e[0]] * e[1], reverse=True)
    last, r = [0] * 4, 0
    for i, (w, c) in enumerate(l):
        if m < w:
            break
        m -= w
        r += c
        last[w] = c
    else:
        return r
    if not m:
        return r
    res, tail = [r], (None, [], [], [])
    for w, c in l[i:]:
        tail[w].append(c)
    for w in 1, 2, 3:
        tail[w].append(0)
    _, t1, t2, t3 = tail
    if m == 1:
        res.append(r + t1[0])
        if last[1]:
            res.append(r - last[1] + t2[0])
        if last[2]:
            res.append(r - last[2] + t3[0])
        if last[3]:
            r -= last[3]
            res += (r + sum(t1[:4]), r + sum(t1[:2]) + t2[0], r + sum(t2[:2]))
    else:  # m == 2
        res += (r + sum(t1[:2]), r + t2[0])
        if last[1]:
            res.append(r - last[1] + t3[0])
        if last[2]:
            res.append(r - last[2] + t3[0] + t1[0])
    return max(res)


def main():
    print(f())


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3

[n, m] = list(map(int, input().strip().split()))
wc = [[] for _ in range(4)]  # w[0] unused
for _ in range(n):
	w, c = list(map(int, input().strip().split()))
	wc[w].append(c)

for i in range(1, 4):
	wc[i].sort(reverse=True)

iwc = [[0 for _ in range(len(wc[i]) + 1)] for i in range(4)]

for i in range(4):
	for j in range(len(wc[i])):
		iwc[i][j + 1] = iwc[i][j] + wc[i][j]

n1 = len(wc[1])
n2 = len(wc[2])
n3 = len(wc[3])

c12 = [(0, 0, 0) for _ in range(m + 1)]
for w in range(len(c12) - 1):
	c, q1, q2 = c12[w]
	c12[w + 1] = max(c12[w + 1], c12[w])
	if q1 < n1:
		c12[w + 1] = max(c12[w + 1], (iwc[1][q1 + 1] + iwc[2][q2], q1 + 1, q2))		
	if q2 < n2 and w + 2 < len(c12):
		c12[w + 2] = max(c12[w + 2], (iwc[1][q1] + iwc[2][q2 + 1], q1, q2 + 1))


cmax = 0
for i in range(n3 + 1):
	if 3 * i > m:
		break
	cmax = max(cmax, iwc[3][i] + c12[m - 3 * i][0])

print(cmax)



#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue, bisect
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
c1, c2, c3 = [0], [0], [0]
for _ in range(n):
    x, y = map(int, input().split())
    if x == 3:
        c3.append(y)
    elif x == 2:
        c2.append(y)
    else:
        c1.append(y)
c1.sort(reverse=True)
c2.sort(reverse=True)
c3.sort(reverse=True)

dp = [None for i in range(m+1)]
dp[0] = (0, 0, 0)
dp[1] = (c1[0], 1, 0)
for i in range(2, m+1):
    if dp[i-1][1] == len(c1):
        x1 = (dp[i-1][0], dp[i-1][1], dp[i-1][2])
    else:
        x1 = (dp[i-1][0]+c1[dp[i-1][1]], dp[i-1][1]+1, dp[i-1][2])
    if dp[i-2][2] == len(c2):
        x2 = (dp[i-2][0], dp[i-2][1], dp[i-2][2])
    else:
        x2 = (dp[i-2][0]+c2[dp[i-2][2]], dp[i-2][1], dp[i-2][2]+1)
    if x1[0] > x2[0]:
        dp[i] = x1
    else:
        dp[i] = x2

ans = 0
cost3 = 0
for i in range(len(c3)):
    cost3 += c3[i-1]
    cap = m - 3*i
    if cap < 0: break
    ans = max(ans, cost3+dp[cap][0])
print(ans)

import sys
n, m = list(map(int, input().split()))
w1 = []
w2 = []
w3 = [10**10]

for w, c in (list(map(int, l.split())) for l in sys.stdin):
    if w == 1:
        w1.append(c)
    elif w == 2:
        w2.append(c)
    else:
        w3.append(c)

w1.sort(reverse=True)
w2.sort(reverse=True)
w3.sort(reverse=True)
w3[0] = 0
w1_size, w2_size = len(w1), len(w2)

dp = [(0, 0, 0) for _ in range(m+3)]
for i in range(m):
    dp[i+1] = max(dp[i+1], dp[i])
    if dp[i][1] < w1_size:
        dp[i+1] = max(dp[i+1], (dp[i][0]+w1[dp[i][1]], dp[i][1]+1, dp[i][2]))
    if dp[i][2] < w2_size:
        dp[i+2] = max(dp[i+2], (dp[i][0]+w2[dp[i][2]], dp[i][1], dp[i][2]+1))

ans = 0
w3_c = 0

for i in range(len(w3)):
    if i*3 > m:
        continue
    w3_c += w3[i]
    ans = max(ans, w3_c + dp[m-i*3][0])

print(ans)


n,m = map(int,input().split())
a = [[],[],[]]
for _ in range(n):
    x,y = map(int,input().split())
    a[x-1].append(y)

for i in range(3):
    a[i].sort(reverse=True)

a_one_odd = []
a_one_even = []
a_length = [len(a[i]) for i in range(3)]
for i in range(0,a_length[0]-1,2):
    a_one_even.append(a[0][i]+a[0][i+1])
for i in range(1,a_length[0]-1,2):
    a_one_odd.append(a[0][i]+a[0][i+1])
data_even = sorted(a_one_even+a[1],reverse=True)
data_odd = sorted(a_one_odd+a[1],reverse=True)

data_sum_even = [0]
for x in data_even:
    data_sum_even.append(data_sum_even[-1]+x)
data_sum_odd = [0]
for x in data_odd:
    data_sum_odd.append(data_sum_odd[-1]+x)

data_sum_three = [0]
for x in a[2]:
    data_sum_three.append(data_sum_three[-1]+x)

ans = 0
#print(data_sum_odd,data_sum_even,data_sum_three)
for k in range(a_length[2]+1):
    if m-3*k < 0:break
    now1,now2 = data_sum_three[k],data_sum_three[k]
    if (m-3*k)%2== 0:
        now1 += data_sum_even[min((m-3*k)//2,len(data_sum_even)-1)]
        if a_length[0] > 0 and m-3*k > 0:
            now2 += a[0][0]
        if (m-3*k)//2 >= 1:
            now2 += data_sum_odd[min((m-3*k)//2-1,len(data_sum_odd)-1)]
    else:
        now1 += data_sum_even[min((m-3*k)//2,len(data_sum_even)-1)]
        if a_length[0] > 0 and m-3*k > 0:
            now2 += a[0][0]
        now2 += data_sum_odd[min((m-3*k-1)//2,len(data_sum_odd)-1)]
    ans = max(ans,now1,now2)


print(ans)