{"raw_statement":[{"iden":"problem statement","content":"Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.  \nThere are $N$ kinds of cheese in front of him.  \nThe deliciousness of the $i$\\-th kind of cheese is $A_i$ per gram, and $B_i$ grams of this cheese are available.  \nThe deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.  \nHowever, using too much cheese would make his boss angry, so the pizza can have at most $W$ grams of cheese on top of it.  \nUnder this condition, find the maximum possible deliciousness of the pizza."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\le N \\le 3 \\times 10^5$\n*   $1 \\le W \\le 3 \\times 10^8$\n*   $1 \\le A_i \\le 10^9$\n*   $1 \\le B_i \\le 1000$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $W$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"3 5\n3 1\n4 2\n2 3"},{"iden":"sample output 1","content":"15\n\nThe optimal choice is to use $1$ gram of cheese of the first kind, $2$ grams of the second kind, and $2$ grams of the third kind.  \nThe pizza will have a deliciousness of $15$."},{"iden":"sample input 2","content":"4 100\n6 2\n1 5\n3 9\n8 7"},{"iden":"sample output 2","content":"100\n\nThere may be less than $W$ grams of cheese in total."},{"iden":"sample input 3","content":"10 3141\n314944731 649\n140276783 228\n578012421 809\n878510647 519\n925326537 943\n337666726 611\n879137070 306\n87808915 39\n756059990 244\n228622672 291"},{"iden":"sample output 3","content":"2357689932073"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}