Read problems statements in Mandarin Chinese and Russian as well. 

Mike takes part in programming contests. His favourite topic is dynamic programming(DP). As he said, that he likes problems on DP, because "you spend a lot of time on thinking and a little time on coding".
In this problem you are to solve a version of the knapsack problem(link), one of the most famous examples of DP problem.
You are given N items, each has two parameters: a weight and a cost. Let's define M as the sum of the weights of all the items.
Your task is to determine the most expensive cost of a knapsack, which capacity equals to 1, 2, ..., M. A cost of a knapsack equals to the sum of the costs of all the elements of the knapsack. Also, when you have a knapsack with a capacity is equal to C, then you can fill it with items, whose sum of weights is not greater than C.

------ Input ------ 

The first line of the input contains one integer N, denoting the number of the items.
The next N lines contain two integers W and C each, denoting the weight and the cost of the corresponding item.

------ Output ------ 

For each capacity C (1 ≤ C ≤ M) of the knapsack, output a single integer - the most expensive cost for that capacity.

------ Constraints ------ 

3 ≤ N ≤ 100000;
1 ≤ W ≤ 2, for each item;
1 ≤ C ≤ 10^{9}, for each item.

------ Example ------ 

Input:
5
1 1
2 2
2 3
2 4
2 5

Output:
1 5 6 9 10 12 13 14 15 

------ Explanations ------ 

In the test case, M equals to 9.

For C = 1, it's optimal to choose {1} items;

For C = 2, it's optimal to choose {5} items;

For C = 3, it's optimal to choose {1, 5} items;

For C = 4, it's optimal to choose {4, 5} items;

For C = 5, it's optimal to choose {1, 4, 5} items;

For C = 6, it's optimal to choose {3, 4, 5} items;

For C = 7, it's optimal to choose {1, 3, 4, 5} items;

For C = 8, it's optimal to choose {2, 3, 4, 5} items;

For C = 9, it's optimal to choose {1, 2, 3, 4, 5} items.

Difficulty: HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
test = False
N = int(input())
ones = []
twos = []
for i in range(N):
	(W, C) = map(int, input().strip().split(' '))
	if test:
		print('W, C = ', W, C)
	if W == 1:
		ones.append(C)
	else:
		twos.append(C)
max_weight = len(ones) + 2 * len(twos)
if len(ones) >= 1:
	ones.append(0)
	ones.sort(reverse=True)
	even_twos = twos.copy()
	odd_twos = twos.copy()
	for i in range(1, len(ones)):
		if i % 2 == 1:
			even_twos.append(ones[i] + ones[i - 1])
		else:
			odd_twos.append(ones[i] + ones[i - 1])
	even_twos = sorted(even_twos)
	odd_twos = sorted(odd_twos)
	res = [0, ones[0]]
	for w in range(2, max_weight + 1):
		if w % 2 == 0:
			temp = even_twos.pop()
		else:
			temp = odd_twos.pop()
		res.append(res[w - 2] + temp)
else:
	res = [0, 0]
	twos = sorted(twos)
	for w in range(2, max_weight + 1):
		temp = 0
		if w % 2 == 0:
			temp = twos.pop()
		res.append(max(res[w - 2] + temp, res[w - 1]))
res.pop(0)
print(*res, sep=' ')


n = int(input())
cost = [[], []]
for i in range(n):
	(w, c) = map(int, input().split())
	cost[w - 1].append(c)
cost[0].sort()
cost[1].sort()
l1 = len(cost[0])
l2 = len(cost[1])
m = l1 + 2 * l2
mp1 = [0 for i in range(m + 1)]
mp2 = [0 for i in range(m + 1)]
mp1[0] = l1
mp2[0] = l2
dp = [0 for i in range(m + 1)]
if l1:
	dp[1] = cost[0][-1]
	mp1[1] = l1 - 1
mp2[1] = l2
for i in range(2, m + 1):
	(sum1, sum2) = (dp[i - 1], dp[i - 2])
	if mp1[i - 1]:
		x1 = mp1[i - 1] - 1
		sum1 = dp[i - 1] + cost[0][x1]
	if mp2[i - 2]:
		x2 = mp2[i - 2] - 1
		sum2 = dp[i - 2] + cost[1][x2]
	if sum1 > sum2:
		mp1[i] = x1
		mp2[i] = mp2[i - 1]
		dp[i] = sum1
	if sum1 <= sum2:
		mp2[i] = x2
		mp1[i] = mp1[i - 2]
		dp[i] = sum2
print(*dp[1:])


def answer():
	n = len(a) + 2 * len(b)
	dp = [[0, 0, 0] for i in range(n + 1)]
	if len(a):
		dp[1] = [a[-1], 1, 0]
	for i in range(2, n + 1):
		x1 = dp[i - 1][0]
		if dp[i - 1][1] < len(a):
			x1 += a[-dp[i - 1][1] - 1]
		x2 = dp[i - 2][0]
		if dp[i - 2][2] < len(b):
			x2 += b[-dp[i - 2][2] - 1]
		if x1 > x2:
			dp[i][0] = x1
			dp[i][1] = dp[i - 1][1] + 1
			dp[i][2] = dp[i - 1][2]
		else:
			dp[i][0] = x2
			dp[i][1] = dp[i - 2][1]
			dp[i][2] = dp[i - 2][2] + 1
	for i in range(1, n + 1):
		print(dp[i][0], end=' ')
n = int(input())
(a, b) = ([], [])
for i in range(n):
	(w, c) = map(int, input().split())
	if w == 1:
		a.append(c)
	else:
		b.append(c)
a.sort()
b.sort()
answer()


import copy
import sys
MAX_REC = 1000000000
sys.setrecursionlimit(MAX_REC)
n = int(input())
w_vec = [0 for _ in range(n)]
c_vec = [0 for _ in range(n)]
n_ones = 0
n_twos = 0
for i in range(n):
	wc = input().split(' ')
	w = int(wc[0])
	c = int(wc[1])
	w_vec[i] = w
	c_vec[i] = c
	if w == 1:
		n_ones += 1
	elif w == 2:
		n_twos += 1
m_max = sum(w_vec)
c_ones = [0 for _ in range(n_ones)]
c_twos = [0 for _ in range(n_twos)]
o_index = 0
t_index = 0
for i in range(n):
	if w_vec[i] == 1:
		c_ones[o_index] = c_vec[i]
		o_index += 1
	elif w_vec[i] == 2:
		c_twos[t_index] = c_vec[i]
		t_index += 1
c_ones.sort()
c_twos.sort()
c_ones_2 = copy.deepcopy(c_ones)
c_twos_2 = copy.deepcopy(c_twos)
res = [0 for _ in range(0, m_max + 1)]
if len(c_ones_2) > 0:
	res[1] = c_ones_2.pop()
even_sum = 0
for m in range(2, m_max + 1, 2):
	t1 = sum(c_ones[-2:])
	t2 = sum(c_twos[-1:])
	if t1 > t2:
		even_sum += t1
		res[m] = even_sum
		if len(c_ones) > 0:
			c_ones.pop()
		if len(c_ones) > 0:
			c_ones.pop()
	else:
		even_sum += t2
		res[m] = even_sum
		if len(c_twos) > 0:
			c_twos.pop()
even_sum = res[1]
for m in range(3, m_max + 1, 2):
	t1 = sum(c_ones_2[-2:])
	t2 = sum(c_twos_2[-1:])
	if t1 > t2:
		even_sum += t1
		res[m] = even_sum
		if len(c_ones_2) > 0:
			c_ones_2.pop()
		if len(c_ones_2) > 0:
			c_ones_2.pop()
	else:
		even_sum += t2
		res[m] = even_sum
		if len(c_twos_2) > 0:
			c_twos_2.pop()
res = [str(r) for r in res]
res = ' '.join(res[1:])
print(res)


def solve(oneWP, twoWP, C):
	newOneWP = sorted(oneWP, reverse=True)
	newTwoWP = sorted(twoWP, reverse=True)
	dp = {}
	used = {}
	for i in range(C):
		dp[i] = dp.get(i, 0)
		used[i] = (0, 0)
	if len(newOneWP) > 0:
		dp[0] = newOneWP[0]
		used[0] = (1, 0)
	cost2 = 0
	cost1 = 0
	cost3 = dp[0]
	if len(newTwoWP) > 0:
		cost2 = newTwoWP[0]
	if len(newOneWP) >= 2:
		cost1 = dp[0] + newOneWP[1]
	maxCost = max(cost1, cost2, cost3)
	if maxCost == cost1:
		dp[1] = cost1
		used[1] = (2, 0)
	elif maxCost == cost2:
		dp[1] = cost2
		used[1] = (0, 1)
	else:
		dp[1] = cost3
		used[1] = (1, 0)
	for i in range(2, C):
		cost1 = 0
		cost2 = 0
		if len(newOneWP) > used[i - 1][0]:
			cost1 = dp[i - 1] + newOneWP[used[i - 1][0]]
		if len(newTwoWP) > used[i - 2][1]:
			cost2 = dp[i - 2] + newTwoWP[used[i - 2][1]]
		cost3 = dp[i - 1]
		dp[i] = max(cost1, cost2, cost3)
		if dp[i] == cost1:
			used[i] = (used[i - 1][0] + 1, used[i - 1][1])
		elif dp[i] == cost2:
			used[i] = (used[i - 2][0], used[i - 2][1] + 1)
		else:
			used[i] = used[i - 1]
	for i in dp:
		print(dp[i], end=' ')
n = int(input())
weights = []
twoWP = []
oneWP = []
for i in range(n):
	(w, c) = map(int, input().split())
	weights.append(w)
	if w == 1:
		oneWP.append(c)
	else:
		twoWP.append(c)
solve(oneWP, twoWP, sum(weights))


N = int(input())
ones = []
twos = []
max_w = 0
for _ in range(N):
	(w, c) = map(int, input().split())
	max_w += w
	if w == 1:
		ones.append(c)
	else:
		twos.append(c)
if len(ones) >= 1:
	ones.append(0)
	ones = sorted(ones, reverse=True)
	even_twos = twos.copy()
	odd_twos = twos.copy()
	for i in range(1, len(ones)):
		if i % 2 == 1:
			even_twos.append(ones[i] + ones[i - 1])
		else:
			odd_twos.append(ones[i] + ones[i - 1])
	even_twos = sorted(even_twos)
	odd_twos = sorted(odd_twos)
	ans = [0, ones[0]]
	for w in range(2, max_w + 1):
		if w % 2 == 0:
			temp = even_twos.pop()
		else:
			temp = odd_twos.pop()
		ans.append(ans[w - 2] + temp)
else:
	ans = [0, 0]
	twos = sorted(twos)
	for w in range(2, max_w + 1):
		temp = 0
		if w % 2 == 0:
			temp = twos.pop()
		ans.append(max(ans[w - 2] + temp, ans[w - 1]))
print(' '.join([str(x) for x in ans[1:]]))


def printArray(A, start, end):
	for i in range(start, end + 1):
		print(A[i], end=' ')
	print()
n = int(input())
itemsOfWeight1 = []
itemsOfWeight2 = []
m = 0
for i in range(n):
	(w, c) = [int(x) for x in input().split()]
	if w == 1:
		itemsOfWeight1.append({'weight': w, 'cost': c})
	else:
		itemsOfWeight2.append({'weight': w, 'cost': c})
	m += w
itemsOfWeight1.sort(key=lambda item: item['cost'], reverse=True)
itemsOfWeight2.sort(key=lambda item: item['cost'], reverse=True)
maxCost = [0 for x in range(m + 1)]
itemsUsed = [{'ones': -1, 'twos': -1} for x in range(m + 1)]
if len(itemsOfWeight1) != 0:
	maxCost[1] = itemsOfWeight1[0]['cost']
	itemsUsed[1] = {'ones': 0, 'twos': -1}
for c in range(2, m + 1):
	nextItemOfWeight1 = itemsUsed[c - 1]['ones'] + 1
	nextItemOfWeight2 = itemsUsed[c - 2]['twos'] + 1
	itemOfWeight1Remaining = nextItemOfWeight1 < len(itemsOfWeight1)
	itemOfWeight2Remaining = nextItemOfWeight2 < len(itemsOfWeight2)
	if itemOfWeight2Remaining:
		maxCost[c] = maxCost[c - 2] + itemsOfWeight2[nextItemOfWeight2]['cost']
		itemsUsed[c] = {'ones': itemsUsed[c - 2]['ones'], 'twos': nextItemOfWeight2}
	if itemOfWeight1Remaining:
		possibleCost = maxCost[c - 1] + itemsOfWeight1[nextItemOfWeight1]['cost']
		if possibleCost > maxCost[c]:
			maxCost[c] = possibleCost
			itemsUsed[c] = {'ones': nextItemOfWeight1, 'twos': itemsUsed[c - 1]['twos']}
	else:
		possibleCost = maxCost[c - 1]
		if possibleCost > maxCost[c]:
			maxCost[c] = possibleCost
			itemsUsed[c] = {'ones': itemsUsed[c - 1]['ones'], 'twos': itemsUsed[c - 1]['twos']}
printArray(maxCost, 1, len(maxCost) - 1)


import sys
from collections import Counter
import numpy as np
import math
test = False
N = int(input().strip())
ones = []
twos = []
for i in range(N):
	(W, C) = map(int, input().strip().split(' '))
	if test:
		print('W, C = ', W, C)
	if W == 1:
		ones.append(C)
	else:
		twos.append(C)
max_weight = len(ones) + 2 * len(twos)
if len(ones) >= 1:
	ones.append(0)
	ones = sorted(ones, reverse=True)
	even_twos = twos.copy()
	odd_twos = twos.copy()
	for i in range(1, len(ones)):
		if i % 2 == 1:
			even_twos.append(ones[i] + ones[i - 1])
		else:
			odd_twos.append(ones[i] + ones[i - 1])
	even_twos = sorted(even_twos)
	odd_twos = sorted(odd_twos)
	answer = [0, ones[0]]
	for w in range(2, max_weight + 1):
		if w % 2 == 0:
			temp = even_twos.pop()
		else:
			temp = odd_twos.pop()
		answer.append(answer[w - 2] + temp)
else:
	answer = [0, 0]
	twos = sorted(twos)
	for w in range(2, max_weight + 1):
		temp = 0
		if w % 2 == 0:
			temp = twos.pop()
		answer.append(max(answer[w - 2] + temp, answer[w - 1]))
print(' '.join([str(x) for x in answer[1:]]))


try:
	n = int(input())
	w1 = []
	w2 = []
	for i in range(n):
		(wi, ci) = [int(x) for x in input().split()]
		if wi == 2:
			w2.append(ci)
		else:
			w1.append(ci)
	w1.sort()
	w2.sort()
	w1o = w1.copy()
	w2o = w2.copy()
	m = len(w2) * 2 + len(w1)
	curr = 0
	ans = [0 for i in range(m + 1)]
	for w in range(2, m + 1, 2):
		cost1 = 0
		cost2 = 0
		flag = 0
		if len(w2) >= 1:
			cost1 = w2[-1]
		if len(w1) >= 2:
			cost2 = w1[-1] + w1[-2]
			flag = 2
		elif len(w1) >= 1:
			cost2 = w1[-1]
			flag = 1
		if cost1 > cost2:
			curr += cost1
			ans[w] = curr
			w2.pop()
		else:
			curr += cost2
			ans[w] = curr
			while flag > 0:
				w1.pop()
				flag -= 1
	curr = 0
	if len(w1o) >= 1:
		curr = w1o.pop()
		ans[1] = curr
	ans[1] = curr
	w1 = w1o
	w2 = w2o
	for w in range(3, m + 1, 2):
		cost1 = 0
		cost2 = 0
		flag = 0
		if len(w2) >= 1:
			cost1 = w2[-1]
		if len(w1) >= 2:
			cost2 = w1[-1] + w1[-2]
			flag = 2
		elif len(w1) >= 1:
			cost2 = w1[-1]
			flag = 1
		if cost1 > cost2:
			curr += cost1
			ans[w] = curr
			w2.pop()
		else:
			curr += cost2
			ans[w] = curr
			while flag > 0:
				w1.pop()
				flag -= 1
	print(' '.join([str(c) for c in ans[1:]]))
except:
	pass


n = int(input())
W1 = []
W2 = []
m = 0
for i in range(n):
	(c, w) = list(map(int, input().split()))
	if c == 1:
		W1.append(w)
	else:
		W2.append(w)
	m += c
W1.sort()
W2.sort()
ans = [None for i in range(m + 1)]
cur = 0
(w1, w2) = (W1[:], W2[:])
for i in range(2, m + 1, 2):
	(c1, c2) = (0, 0)
	flag = 1
	if len(w1) >= 2:
		c1 = sum(w1[-2:])
	elif len(w1) >= 1:
		c1 = w1[-1]
		flag = 0
	if len(w2) >= 1:
		c2 = w2[-1]
	if c1 > c2:
		cur += c1
		w1.pop()
		if flag:
			w1.pop()
	else:
		cur += c2
		w2.pop()
	ans[i] = str(cur)
(w1, w2) = (W1[:], W2[:])
cur = 0
if len(w1) >= 1:
	cur = w1.pop()
ans[1] = str(cur)
for i in range(3, m + 1, 2):
	(c1, c2) = (0, 0)
	flag = 1
	if len(w1) >= 2:
		c1 = sum(w1[-2:])
	elif len(w1) >= 1:
		c1 = w1[-1]
		flag = 0
	if len(w2) >= 1:
		c2 = w2[-1]
	if c1 < c2:
		cur += c2
		w2.pop()
	else:
		cur += c1
		w1.pop()
		if flag:
			w1.pop()
	ans[i] = str(cur)
print(' '.join(ans[1:]))


try:
	n = int(input())
	one = []
	two = []
	tw = 0
	for _ in range(n):
		(w, c) = map(int, input().split())
		tw += w
		if w == 1:
			one.append(c)
		else:
			two.append(c)
	one = sorted(one, reverse=True)
	two = sorted(two, reverse=True)
	onet = one.copy()
	twot = two.copy()
	dp = [0] * (tw + 1)
	cur = 0
	for i in range(2, tw + 1, 2):
		cost = [0, 0, 0]
		if two:
			cost[0] = two[0]
		if len(one) > 1:
			cost[1] = one[0] + one[1]
		elif len(one) == 1:
			cost[2] = one[0]
		maxk = cost.index(max(cost))
		if maxk == 0:
			two.pop(0)
		elif maxk == 1:
			one.pop(0)
			one.pop(0)
		else:
			one.pop(0)
		cur += cost[maxk]
		dp[i] = cur
	cur = 0
	one = onet
	two = twot
	if len(one) >= 1:
		k = one.pop(0)
		dp[1] = k
		cur = k
	for i in range(3, tw + 1, 2):
		cost = [0, 0, 0]
		if two:
			cost[0] = two[0]
		if len(one) > 1:
			cost[1] = one[0] + one[1]
		elif len(one) == 1:
			cost[2] = one[0]
		maxk = cost.index(max(cost))
		if maxk == 0:
			two.pop(0)
		elif maxk == 1:
			one.pop(0)
			one.pop(0)
		else:
			one.pop(0)
		cur += cost[maxk]
		dp[i] = cur
	print(*dp[1:])
except:
	pass


n = int(input())
(one, two) = ([], [])
W = 0
for _ in range(n):
	(w, c) = map(int, input().split())
	if w == 1:
		one.append(c)
	else:
		two.append(c)
	W += w
e_one = sorted(one)
e_two = sorted(two)
ans = [0] * W
temp = 0
for w in range(2, W + 1, 2):
	(cost1, cost2) = (0, 0)
	if len(e_one) >= 2:
		cost1 = e_one[-1] + e_one[-2]
	elif len(e_one) >= 1:
		cost1 = e_one[-1]
	if len(e_two) >= 1:
		cost2 = e_two[-1]
	if cost1 >= cost2:
		if len(e_one) >= 2:
			e_one.pop()
			e_one.pop()
		elif len(e_one) >= 1:
			e_one.pop()
		temp += cost1
	else:
		e_two.pop()
		temp += cost2
	ans[w - 1] = temp
o_one = sorted(one)
o_two = sorted(two)
temp = 0
if len(o_one) >= 1:
	ans[0] = o_one.pop()
	temp = ans[0]
for w in range(3, W + 1, 2):
	(cost1, cost2) = (0, 0)
	if len(o_one) >= 2:
		cost1 = o_one[-1] + o_one[-2]
	elif len(o_one) >= 1:
		cost1 = o_one[-1]
	if len(o_two) >= 1:
		cost2 = o_two[-1]
	if cost1 >= cost2:
		if len(o_one) >= 2:
			o_one.pop()
			o_one.pop()
		elif len(o_one) >= 1:
			o_one.pop()
		temp += cost1
	else:
		o_two.pop()
		temp += cost2
	ans[w - 1] = temp
print(*ans, sep=' ')


from sys import stdin
n = int(stdin.readline())
list1 = []
list2 = []
m = 0
sum1 = 0
pop = ()
for i in range(n):
	(w, c) = list(map(int, stdin.readline().split()))
	if w == 1:
		list1.append((w, c))
		m += w
	else:
		list2.append((w, c))
		m += w
list1.sort(reverse=True, key=lambda x: x[1])
list2.sort(reverse=True, key=lambda x: x[1])
e_list1 = list1[:]
e_list2 = list2[:]
max1 = [0] * m
if list1 != []:
	sum1 += list1.pop(0)[1]
	max1[0] = sum1
else:
	max1[0] = sum1
for i in range(2, m, 2):
	c = i + 1
	if list1 != []:
		if list2 != [] and len(list1) >= 2:
			if list2[0][1] >= list1[0][1] + list1[1][1]:
				sum1 += list2[0][1]
				max1[i] = sum1
				list2.pop(0)
			else:
				sum1 += list1[0][1]
				list1.pop(0)
				sum1 += list1[0][1]
				max1[i] = sum1
				list1.pop(0)
		elif list2 != [] and len(list1) == 1:
			if list2[0][1] >= list1[0][1]:
				sum1 += list2[0][1]
				max1[i] = sum1
				list2.pop(0)
			else:
				sum1 += list1[0][1]
				max1[i] = sum1
				list1.pop(0)
		elif list2 == []:
			if len(list1) >= 2:
				sum1 += list1[0][1]
				list1.pop(0)
				sum1 += list1[0][1]
				max1[i] = sum1
				list1.pop(0)
			else:
				sum1 += list1[0][1]
				max1[i] = sum1
				list1.pop(0)
	elif list2 != []:
		sum1 += list2[0][1]
		max1[i] = sum1
		list2.pop(0)
sum1 = 0
for i in range(1, m, 2):
	c = i + 1
	if e_list1 != []:
		if e_list2 != [] and len(e_list1) >= 2:
			if e_list2[0][1] >= e_list1[0][1] + e_list1[1][1]:
				sum1 += e_list2[0][1]
				max1[i] = sum1
				e_list2.pop(0)
			else:
				sum1 += e_list1[0][1]
				e_list1.pop(0)
				sum1 += e_list1[0][1]
				max1[i] = sum1
				e_list1.pop(0)
		elif e_list2 != [] and len(e_list1) == 1:
			if e_list2[0][1] >= e_list1[0][1]:
				sum1 += e_list2[0][1]
				max1[i] = sum1
				e_list2.pop(0)
			else:
				sum1 += e_list1[0][1]
				max1[i] = sum1
				e_list1.pop(0)
		elif e_list2 == []:
			if len(e_list1) >= 2:
				sum1 += e_list1[0][1]
				e_list1.pop(0)
				sum1 += e_list1[0][1]
				max1[i] = sum1
				e_list1.pop(0)
			else:
				sum1 += e_list1[0][1]
				max1[i] = sum1
				e_list1.pop(0)
	elif e_list2 != []:
		sum1 += e_list2[0][1]
		max1[i] = sum1
		e_list2.pop(0)
for (j, val) in enumerate(max1):
	print(val, end=' ')


from sys import stdin
n = int(stdin.readline())
list1 = []
weight = 0
list_one = []
list_two = []
for i in range(n):
	(w, c) = map(int, stdin.readline().split())
	if w == 1:
		list_one.append(c)
	else:
		list_two.append(c)
	weight += w
list1 = [0] * weight
list_one.sort(reverse=True)
list_two.sort(reverse=True)
list_one_even = list_one[:]
list_two_even = list_two[:]
curr = 0
for i in range(2, weight + 1, 2):
	if list_two_even != [] and len(list_one_even) >= 1:
		if len(list_one_even) > 1 and list_two_even[0] >= list_one_even[0] + list_one_even[1]:
			cost = list_two_even.pop(0)
			curr += cost
			list1[i - 1] = curr
		elif len(list_one_even) == 1 and list_two_even[0] >= list_one_even[0]:
			cost = list_two_even.pop(0)
			curr += cost
			list1[i - 1] = curr
		elif len(list_one_even) > 1:
			cost1 = list_one_even.pop(0)
			cost2 = list_one_even.pop(0)
			curr += cost1 + cost2
			list1[i - 1] = curr
		else:
			cost = list_one_even.pop(0)
			curr += cost
			list1[i - 1] = curr
	elif list_two_even == []:
		if len(list_one_even) > 1:
			cost1 = list_one_even.pop(0)
			cost2 = list_one_even.pop(0)
			curr += cost1 + cost2
			list1[i - 1] = curr
		else:
			cost = list_one_even.pop(0)
			curr += cost
			list1[i - 1] = curr
	elif list_one_even == []:
		if len(list_two_even) > 0:
			cost = list_two_even.pop(0)
			curr += cost
			list1[i - 1] = curr
if len(list_one) > 0:
	list1[0] = list_one.pop(0)
	curr = list1[0]
else:
	curr = 0
for i in range(3, weight + 1, 2):
	if list_two != [] and len(list_one) >= 1:
		if len(list_one) > 1 and list_two[0] >= list_one[0] + list_one[1]:
			cost = list_two.pop(0)
			curr += cost
			list1[i - 1] = curr
		elif len(list_one) == 1 and list_two[0] >= list_one[0]:
			cost = list_two.pop(0)
			curr += cost
			list1[i - 1] = curr
		elif len(list_one) > 1:
			cost1 = list_one.pop(0)
			cost2 = list_one.pop(0)
			curr += cost1 + cost2
			list1[i - 1] = curr
		else:
			cost = list_one.pop(0)
			curr += cost
			list1[i - 1] = curr
	elif list_two == []:
		if len(list_one) > 1:
			cost1 = list_one.pop(0)
			cost2 = list_one.pop(0)
			curr += cost1 + cost2
			list1[i - 1] = curr
		else:
			cost = list_one.pop(0)
			curr += cost
			list1[i - 1] = curr
	elif list_one == []:
		if len(list_two) > 0:
			cost = list_two.pop(0)
			curr += cost
			list1[i - 1] = curr
print(' '.join(map(str, list1)))


(n, a, b, MaxW, MaxC) = (int(input()), list(), list(), 0, 0)
for _ in range(n):
	(w, c) = map(int, input().split())
	a.append(c) if w == 1 else b.append(c)
	(MaxW, MaxC) = (MaxW + w, MaxC + c)
(a, b, c, x, y) = (sorted(a), sorted(b), [0] * (MaxW + 1), [0] * (MaxW + 1), [0] * (MaxW + 1))
c[MaxW] = MaxC
for i in range(MaxW, 1, -1):
	if y[i] < len(b) and c[i] - b[y[i]] > c[i - 1]:
		(c[i - 1], x[i - 1], y[i - 1]) = (c[i] - b[y[i]], x[i], y[i] + 1)
	if y[i] < len(b) and c[i] - b[y[i]] > c[i - 2]:
		(c[i - 2], x[i - 2], y[i - 2]) = (c[i] - b[y[i]], x[i], y[i] + 1)
	if x[i] < len(a) and c[i] - a[x[i]] > c[i - 1]:
		(c[i - 1], x[i - 1], y[i - 1]) = (c[i] - a[x[i]], x[i] + 1, y[i])
for i in range(1, MaxW + 1):
	print(c[i], end=' ')


n = int(input())
m = 0
item1 = []
item2 = []
for i in range(n):
	(w, c) = map(int, input().split())
	m += w
	if w == 1:
		item1.append(c)
	if w == 2:
		item2.append(c)
item1 = sorted(item1, reverse=True)
item2 = sorted(item2, reverse=True)
ans = [0] * (m + 1)
curr = 0
l1 = len(item1)
l2 = len(item2)
(one, two) = (0, 0)
for i in range(2, m + 1, 2):
	if one + 1 < l1 and two < l2:
		if item1[one + 1] + item1[one] > item2[two]:
			curr += item1[one] + item1[one + 1]
			ans[i] = curr
			one += 2
		else:
			curr += item2[two]
			two += 1
			ans[i] = curr
	elif one < l1 and two < l2:
		if item1[one] > item2[two]:
			curr += item1[one]
			one += 1
			ans[i] = curr
		else:
			curr += item2[two]
			two += 1
			ans[i] = curr
	elif one + 1 < l1:
		curr += item1[one] + item1[one + 1]
		one += 2
		ans[i] = curr
	elif one < l1:
		curr += item1[one]
		one += 1
		ans[i] = curr
	elif two < l2:
		curr += item2[two]
		two += 1
		ans[i] = curr
curr = 0
if l1 > 0:
	ans[1] = item1[0]
	curr = item1[0]
(one, two) = (1, 0)
for i in range(3, m + 1, 2):
	if one + 1 < l1 and two < l2:
		if item1[one + 1] + item1[one] > item2[two]:
			curr += item1[one] + item1[one + 1]
			ans[i] = curr
			one += 2
		else:
			curr += item2[two]
			two += 1
			ans[i] = curr
	elif one < l1 and two < l2:
		if item1[one] > item2[two]:
			curr += item1[one]
			one += 1
			ans[i] = curr
		else:
			curr += item2[two]
			two += 1
			ans[i] = curr
	elif one + 1 < l1:
		curr += item1[one] + item1[one + 1]
		one += 2
		ans[i] = curr
	elif one < l1:
		curr += item1[one]
		one += 1
		ans[i] = curr
	elif two < l2:
		curr += item2[two]
		two += 1
		ans[i] = curr
print(*ans[1:])


n = int(input())
total = 0
w1 = []
w2 = []
for _ in range(n):
	(w, c) = map(int, input().split())
	if w == 1:
		w1.append(c)
	else:
		w2.append(c)
	total += w
w1.sort(reverse=True)
w2.sort(reverse=True)
ans = [0] * (total + 1)
lw1 = len(w1)
lw2 = len(w2)
cur = 0
(one, two) = (0, 0)
for i in range(2, total + 1, 2):
	if one + 1 < lw1 and two < lw2:
		if w1[one + 1] + w1[one] > w2[two]:
			cur += w1[one + 1] + w1[one]
			ans[i] = cur
			one += 2
		else:
			cur += w2[two]
			ans[i] = cur
			two += 1
	elif one < lw1 and two < lw2:
		if w1[one] > w2[two]:
			cur += w1[one]
			ans[i] = cur
			one += 1
		else:
			cur += w2[two]
			ans[i] = cur
			two += 1
	elif one + 1 < lw1:
		cur += w1[one + 1] + w1[one]
		ans[i] = cur
		one += 2
	elif one < lw1:
		cur += w1[one]
		ans[i] = cur
		one += 1
	elif two < lw2:
		cur += w2[two]
		ans[i] = cur
		two += 1
cur = 0
if lw1 > 0:
	cur = w1[0]
	ans[1] = cur
one = 1
two = 0
for i in range(3, total + 1, 2):
	if one + 1 < lw1 and two < lw2:
		if w1[one + 1] + w1[one] > w2[two]:
			cur += w1[one + 1] + w1[one]
			ans[i] = cur
			one += 2
		else:
			cur += w2[two]
			ans[i] = cur
			two += 1
	elif one < lw1 and two < lw2:
		if w1[one] > w2[two]:
			cur += w1[one]
			ans[i] = cur
			one += 1
		else:
			cur += w2[two]
			ans[i] = cur
			two += 1
	elif one + 1 < lw1:
		cur += w1[one + 1] + w1[one]
		ans[i] = cur
		one += 2
	elif one < lw1:
		cur += w1[one]
		ans[i] = cur
		one += 1
	elif two < lw2:
		cur += w2[two]
		ans[i] = cur
		two += 1
print(*ans[1:])


num_items = int(input())
costs_weight1 = []
costs_weight2 = []
total_weight = 0
for i in range(num_items):
	(weight, cost) = map(int, input().split())
	total_weight += weight
	if weight == 1:
		costs_weight1.append(cost)
	else:
		costs_weight2.append(cost)
costs_weight1.sort(reverse=True)
costs_weight2.sort(reverse=True)
max_costs = [0] * (total_weight + 1)
(weight1_index, weight2_index) = (0, 0)
for i in range(2, len(max_costs), 2):
	cost1 = 0
	cost2 = 0
	if weight1_index < len(costs_weight1):
		cost1 += costs_weight1[weight1_index]
	if weight1_index + 1 < len(costs_weight1):
		cost1 += costs_weight1[weight1_index + 1]
	if weight2_index < len(costs_weight2):
		cost2 += costs_weight2[weight2_index]
	if cost1 > cost2:
		max_costs[i] = max_costs[i - 2] + cost1
		weight1_index += 2
	else:
		max_costs[i] = max_costs[i - 2] + cost2
		weight2_index += 1
if len(costs_weight1) != 0:
	max_costs[1] = costs_weight1[0]
(weight1_index, weight2_index) = (1, 0)
for i in range(3, len(max_costs), 2):
	cost1 = 0
	cost2 = 0
	if weight1_index < len(costs_weight1):
		cost1 += costs_weight1[weight1_index]
	if weight1_index + 1 < len(costs_weight1):
		cost1 += costs_weight1[weight1_index + 1]
	if weight2_index < len(costs_weight2):
		cost2 += costs_weight2[weight2_index]
	if cost1 > cost2:
		max_costs[i] = max_costs[i - 2] + cost1
		weight1_index += 2
	else:
		max_costs[i] = max_costs[i - 2] + cost2
		weight2_index += 1
print(' '.join(map(str, max_costs[1:])))


x = []
y = []
m = 0
for _ in range(int(input())):
	(w, c) = map(int, input().split())
	m += w
	if w == 1:
		x.append(c)
	else:
		y.append(c)
if not x:
	x.append(0)
x.sort(reverse=True)
y.sort(reverse=True)
xn = len(x)
yn = len(y)
i = 1
j = 0
tKnapSack = x[0]
print(tKnapSack, end=' ')
for k in range(1, m):
	if j >= yn or (i < xn and (xn == 1 or x[i] + x[i - 1] > y[j])):
		s = x[i]
		tKnapSack += s
		i += 1
	else:
		s = y[j] - x[i - 1]
		tKnapSack += s
		j += 1
		i -= 1
	print(max(tKnapSack, tKnapSack - s), end=' ')
print()


memo = dict()
n = int(input())
(s, l1, l2) = (0, [], [])
for i in range(n):
	(w, p) = map(int, input().split())
	if w == 1:
		l1.append(p)
	else:
		l2.append(p)
	s += w
l1 = sorted(l1)
l2 = sorted(l2)
l1 = l1[::-1]
l2 = l2[::-1]
dupl1 = l1[:]
dupl2 = l2[:]
memo[0] = 0
for i in range(2, s + 1, 2):
	(max2, max1) = (0, 0)
	if len(l2) > 0:
		max2 = l2[0]
	k = True
	if len(l1) > 1:
		max1 = l1[0] + l1[1]
	elif len(l1) == 1:
		max1 = l1[0]
		k = False
	if max2 > max1:
		memo[i] = memo[i - 2] + max2
		l2.pop(0)
	else:
		memo[i] = memo[i - 2] + max1
		if k:
			l1.pop(0)
			l1.pop(0)
		else:
			l1.pop(0)
if len(dupl1) > 0:
	memo[1] = dupl1[0]
	dupl1.pop(0)
else:
	memo[1] = 0
for i in range(3, s + 1, 2):
	(max2, max1) = (0, 0)
	if len(dupl2) > 0:
		max2 = dupl2[0]
	k = True
	if len(dupl1) > 1:
		max1 = dupl1[0] + dupl1[1]
	elif len(dupl1) == 1:
		max1 = dupl1[0]
		k = False
	if max2 > max1:
		memo[i] = memo[i - 2] + max2
		dupl2.pop(0)
	else:
		memo[i] = memo[i - 2] + max1
		if k:
			dupl1.pop(0)
			dupl1.pop(0)
		else:
			dupl1.pop(0)
for i in range(1, s + 1):
	print(memo[i], end=' ')


n = int(input())
l = []
v = 0
o = []
t = []
for w in range(n):
	(p, q) = [int(e) for e in input().split()]
	l.append([q, p])
	v += p
	if p == 1:
		o.append(q)
	else:
		t.append(q)
o.sort(reverse=True)
t.sort(reverse=True)
i = 1
j = 0
k = 1
s = 0
if len(o) == 0:
	o.append(0)
c = o[0]
print(o[0], end=' ')
while k < v:
	if j >= len(t) or (i < len(o) and (len(o) == 1 or o[i] + o[i - 1] > t[j])):
		s = o[i]
		c += s
		i += 1
	else:
		s = t[j] - o[i - 1]
		c += s
		j += 1
		i -= 1
	k += 1
	print(max(c, c - s), end=' ')
print()


n = int(input().strip())
values_of_weight = {1: [], 2: []}
m = 0
for i in range(n):
	(weight, value) = map(int, input().strip().split())
	values_of_weight[weight].append(value)
	m += weight
values_of_weight[1].sort()
values_of_weight[2].sort()
value_dp = [0 for i in range(m + 1)]
idx_1 = len(values_of_weight[1]) - 1
idx_2 = len(values_of_weight[2]) - 1
for capacity in range(2, m + 1, 2):
	if idx_1 >= 0 and idx_2 >= 0:
		if idx_1 == 0:
			if values_of_weight[1][idx_1] > values_of_weight[2][idx_2]:
				value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1]
				idx_1 -= 1
			else:
				value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[2][idx_2]
				idx_2 -= 1
		elif values_of_weight[1][idx_1] + values_of_weight[1][idx_1 - 1] > values_of_weight[2][idx_2]:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1] + values_of_weight[1][idx_1 - 1]
			idx_1 -= 2
		else:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[2][idx_2]
			idx_2 -= 1
	elif idx_2 >= 0:
		value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[2][idx_2]
		idx_2 -= 1
	elif idx_1 >= 0:
		if idx_1 == 0:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1]
			idx_1 -= 1
		else:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1] + values_of_weight[1][idx_1 - 1]
			idx_1 -= 2
if len(values_of_weight[1]) >= 1:
	value_dp[1] = values_of_weight[1].pop()
idx_1 = len(values_of_weight[1]) - 1
idx_2 = len(values_of_weight[2]) - 1
for capacity in range(3, m + 1, 2):
	if idx_1 >= 0 and idx_2 >= 0:
		if idx_1 == 0:
			if values_of_weight[1][idx_1] > values_of_weight[2][idx_2]:
				value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1]
				idx_1 -= 1
			else:
				value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[2][idx_2]
				idx_2 -= 1
		elif values_of_weight[1][idx_1] + values_of_weight[1][idx_1 - 1] > values_of_weight[2][idx_2]:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1] + values_of_weight[1][idx_1 - 1]
			idx_1 -= 2
		else:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[2][idx_2]
			idx_2 -= 1
	elif idx_2 >= 0:
		value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[2][idx_2]
		idx_2 -= 1
	elif idx_1 >= 0:
		if idx_1 == 0:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1]
			idx_1 -= 1
		else:
			value_dp[capacity] = value_dp[capacity - 2] + values_of_weight[1][idx_1] + values_of_weight[1][idx_1 - 1]
			idx_1 -= 2
for idx in range(2, capacity + 1):
	if value_dp[idx] == 0:
		value_dp[idx] = value_dp[idx_1]
print(*value_dp[1:], sep=' ')


from operator import itemgetter
ones = []
twos = []
total_weight = 0
for _ in range(int(input())):
	temp = list(map(int, input().split()))
	if temp[0] == 1:
		ones.append(temp)
	else:
		twos.append(temp)
	total_weight += temp[0]
ones = sorted(ones, key=itemgetter(1), reverse=True)
twos = sorted(twos, key=itemgetter(1), reverse=True)
ans = [0] * (total_weight + 1)
track_twos = 0
track_ones = 0
cur = 0
for w in range(2, total_weight + 1, 2):
	if track_ones + 1 <= len(ones) - 1:
		ones_value = ones[track_ones][1] + ones[track_ones + 1][1]
	elif track_ones == len(ones) - 1:
		ones_value = ones[track_ones][1]
	else:
		ones_value = 0
	if track_twos <= len(twos) - 1:
		twos_value = twos[track_twos][1]
	else:
		twos_value = 0
	if ones_value < twos_value:
		cur += twos_value
		track_twos += 1
	else:
		cur += ones_value
		track_ones += 2
	ans[w] = cur
cur = 0
track_ones = 0
track_twos = 0
if len(ones) >= 1:
	ans[1] = ones[0][1]
	cur += ans[1]
	track_ones += 1
for w in range(3, total_weight + 1, 2):
	if track_ones + 1 <= len(ones) - 1:
		ones_value = ones[track_ones][1] + ones[track_ones + 1][1]
	elif track_ones == len(ones) - 1:
		ones_value = ones[track_ones][1]
	else:
		ones_value = 0
	if track_twos <= len(twos) - 1:
		twos_value = twos[track_twos][1]
	else:
		twos_value = 0
	if ones_value < twos_value:
		cur += twos_value
		track_twos += 1
	else:
		cur += ones_value
		track_ones += 2
	ans[w] = cur
for i in range(1, len(ans)):
	print(ans[i], end=' ')


from copy import deepcopy
n = int(input())
(w1, w2) = ([], [])
m = 0
for i in range(n):
	(w, c) = tuple(map(int, input().split()))
	if w == 1:
		w1.append(c)
	else:
		w2.append(c)
	m += w
w1.sort()
w2.sort()
(W1, W2) = (deepcopy(w1), deepcopy(w2))
ans = [0] * (m + 1)
cur = 0
for w in range(2, m + 1, 2):
	cost1 = cost2 = 0
	if w2:
		cost2 = w2[-1]
	if len(w1) >= 2:
		cost1 += w1[-1] + w1[-2]
	elif w1:
		cost1 += w1[-1]
	if cost2 > cost1:
		cur += cost2
		w2.pop()
	else:
		cur += cost1
		if len(w1) >= 2:
			w1.pop()
			w1.pop()
		else:
			w1.pop()
	ans[w] = cur
(w1, w2, cur) = (W1, W2, 0)
if w1:
	cur = w1[-1]
	w1.pop()
ans[1] = cur
for w in range(3, m + 1, 2):
	cost1 = cost2 = 0
	if w2:
		cost2 = w2[-1]
	if len(w1) >= 2:
		cost1 += w1[-1] + w1[-2]
	elif w1:
		cost1 += w1[-1]
	if cost2 > cost1:
		cur += cost2
		w2.pop()
	else:
		cur += cost1
		if len(w1) >= 2:
			w1.pop()
			w1.pop()
		else:
			w1.pop()
	ans[w] = cur
print(' '.join(map(str, ans[1:])))