#1070. 上课

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Misaka

题目描述

大学开始了,wondove 就要选课上了。

wondove 所在的学校有一个奇怪的上课系统,有 N 种课可以选择,每种课可以重复的上,并且每次上都花掉同样的时间,获得同样的知识量。

wondove 同学每天有一定的上课时间总额,他想获得最大的知识量,你能否告诉他最多能得到多少知识吗?

输入格式

第一行有两个整数 N,M ,表示有 N 种课,他每天有 M 个单位学习时间。

接下来 N 行,每行有两个数 P_i,W_i ,表示第 i 种课所花的时间单位和所获得的知识量。

输出格式

输出一个整数,表示 wondove 同学通过一天的课程学习可能获得的最大知识量。

样例

样例输入

3 11
2 5
3 6
6 18

样例输出

29

数据范围与提示

N \leq 1000, M \leq 1000, P_i \leq 100,W_i \leq 100