题目描述

你有一个背包，最多能容纳的体积是 $V$。

现在有 $n$ 个物品，第 $i$ 个物品的体积为 $v_i$，价值为 $w_i$

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入格式

第一行两个整数 $n$ 和 $V$，表示物品个数和背包体积。

接下来 $n$ 行，每行两个数 $v_i$ 和 $w_i$，表示第 $i$ 个物品的体积和价值。

输出格式

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出 -1。

3 5
2 10
4 5
1 4

14
9

3 8
12 6
11 8
6 8

8
-1

说明

样例1 装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。

样例2 装第三个物品时总价值最大但是不满，装满背包无解。

数据范围

$1≤n,V,v_i,w_i≤1000$