You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小偷啊，你咋这么能偷

题目描述

有一个小偷名叫基德，有一天基德带了一个最大容量为m的背包去偷东西，到了一家商店，发现这家商店里有n个物品可以偷，每个物品有一个体积和价值，基德有一个怪癖，就是背包不装满不爽，所以请聪明的你帮他算算，在偷的总体积等于背包容量的时候输出偷的的物品价值最大，如果有这种方案，请输出最大价值，否则请输出-1

输入格式

第一行两个整数n和m（1<=n<=1000, 10<=m<=1000000） 接下来n行，每行两个整数v和c，分别对应体积和价值(1<=v,c<=10000)

输出格式

一个数

样例 #1

样例输入 #1

6 10
1 1
1 1
1 1
1 1
1 1
1 1

样例输出 #1

-1