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: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []

def hnbhai(tc):
	(n, m) = sd()
	dp = [(0, 0, 0) for i in range(m + 3)]
	gp = [[] for i in range(4)]
	for i in range(n):
		(w, c) = sd()
		gp[w].append(c)
	gp[1].sort(reverse=True)
	gp[2].sort(reverse=True)
	gp[3].sort(reverse=True)
	for i in range(0, m + 1):
		one = dp[i][1]
		two = dp[i][2]
		if one < len(gp[1]):
			if dp[i + 1][0] < dp[i][0] + gp[1][one]:
				dp[i + 1] = (dp[i][0] + gp[1][one], one + 1, two)
		if two < len(gp[2]):
			dp[i + 2] = (dp[i][0] + gp[2][two], one, two + 1)
	for i in range(1, m + 1):
		dp[i] = max(dp[i - 1], dp[i])
	ans = dp[m][0]
	tot = 0
	for i in range(len(gp[3]) + 1):
		if 3 * i <= m:
			ans = max(dp[m - 3 * i][0] + tot, ans)
			if i < len(gp[3]):
				tot += gp[3][i]
	print(ans)
for _ in range(1):
	hnbhai(_ + 1)


(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
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)


def f():
	(n, m) = 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:
		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())
main()


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
(N, M) = 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) = 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))


import sys, math, queue, bisect
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] = list(map(int, input().strip().split()))
wc = [[] for _ in range(4)]
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)


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()


import sys
from itertools import accumulate
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
items = [[], [], [], []]
for (w, c) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	items[w].append(c)
for i in range(1, 4):
	items[i].sort(reverse=True)
(n_w1, n_w2) = (len(items[1]), len(items[2]))
dp = [0] * (m + 3)
(dp_w1, dp_w2) = ([0] * (m + 3), [0] * (m + 3))
for i in range(m + 1):
	if i > 0 and dp[i - 1] > dp[i]:
		dp[i] = dp[i - 1]
		(dp_w1[i], dp_w2[i]) = (dp_w1[i - 1], dp_w2[i - 1])
	if dp_w1[i] < n_w1 and dp[i + 1] < dp[i] + items[1][dp_w1[i]]:
		dp[i + 1] = dp[i] + items[1][dp_w1[i]]
		dp_w1[i + 1] = dp_w1[i] + 1
		dp_w2[i + 1] = dp_w2[i]
	if dp_w2[i] < n_w2 and dp[i + 2] < dp[i] + items[2][dp_w2[i]]:
		dp[i + 2] = dp[i] + items[2][dp_w2[i]]
		dp_w1[i + 2] = dp_w1[i]
		dp_w2[i + 2] = dp_w2[i] + 1
items[3] = [0] + list(accumulate(items[3]))
ans = 0
for i in range(len(items[3])):
	if i * 3 > m:
		break
	ans = max(ans, items[3][i] + dp[m - i * 3])
print(ans)


(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)


(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))