你有一个背包，最大容量为 。现有 件物品，第 件物品的体积为 ，价值为 。研究人员提出以下两种装填方案： 不要求装满背包，求能获得的最大总价值； 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 。

输入描述:

第一行输入两个整数 和 ，分别表示物品数量与背包容量。 此后 行，第 行输入两个整数 ，分别表示第 件物品的体积与价值。

输出描述:

输出两行： 第一行输出方案 的答案； 第二行输出方案 的答案（若无解输出 ）。

备注:

要求  的时间复杂度， 空间复杂度。