Pipe Cutting
By Lucas Hermann Negri, Universidade Tecnológica Federal - Paraná 
Brazil
By Lucas Hermann Negri, Universidade Tecnológica Federal - Paraná Brazil
OBI (Brazilian Organization of Facilities) is a company that produces pipes and fitters. The production technique used at OBI always produces long pipes, which are then cut to satisfy client needs.
Their clients have different applications, so they need pipes with different lengths. When the company was small and the clients were few, all the pipe cut planning process (to maximize profit) was done by a very dedicated employee. However, with the increase on the number of orders, it became prohibitive. That's where you come in: hired by OBI, your task is to write a program that, given the relation between the pipes' length and its respective sales value, determine the greatest possible value that can be obtained by cutting and selling a pipe with a determined initial length. Pipe lengths can be repeated, and there can be leftovers.
The first line of input has two integers: N (0 ≤ N ≤ 1000) that indicates the number of different pipe sizes and T (0 ≤ T ≤ 2000), that is the size of each pipe produced by OBI.
Each of the following N lines has two integers: Ci and Vi (1 ≤ Ci, Vi ≤ 5000, 1 ≤ i ≤ N), representing, respectively, the lenght and the sales value of a client ordered pipe i.
For each test case, print in one line the greatest possible value that can be obtained by cutting and selling a pipe with original length T.
| Input Sample | Output Sample |
|
3 10 |
5 |