问题描述

已知n个物品，其中，第i(i∈1..n)个物品的价值为vi(vi∈ℝ)，质量为wi(wi∈ℕ)。已知背包容量为K(K∈ℕ)。每个物品要么整个放入背包要么不放入背包，求，把哪些物品放入背包，才能让背包中物品的价值最大。

令xi=1代表把第i个物品放入背包，xi=0代表不把第i个物品放入背包，则该问题可以用以下数学语言进行描述。

目标函数 maximize:∑i=1nvixi(1)

满足 ∑i=1nwixi≤Kxi∈{0,1},i∈1..n(2) 输入数据

数据通过标准输入进行输入，格式如下。

n K v_1 w_1 v_2 w_2 ... v_n w_n 第一行两个整数，分别为物品总数n（n <= 2000000000）和背包容量K（K <= 18446744073709551616）。接下来n行，每一行两个整数v_i和w_i分别描述第i件物品的价值和重量。

输出数据

输出数据通过标准输出进行输出，格式如下。

obj x_1 x_2 ... x_n 第一行一个整数，该整数是目标函数的值（装入背包物品的总重量）。第二行n个数字，分别代表第i个物品是否放入背包（1代表放入，0代表不放）。

输入输出实例

输入

4 12 8 4 10 5 15 8 4 3 输出

19 0 0 1 1 显然，该输出结果并非最优解。像这种满足(2)式的解，我们称为“可满足解”。让(1)式获得最大值的解，我们称为“最优解”。