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.

题目描述

新学期开始了，小Y就要选课上了。

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

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

输入格式

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

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

输出格式

只有一个整数S，表示小Y同学通过一天的课程学习可能获得的最大知识量。

样例数据

input

3 11

2 5

3 6

6 18

output

29

数据规模与约定

100%的数据保证$N≤1000，M≤1000，Pi≤100，Wi≤100$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$