{"raw_statement":[{"iden":"statement","content":"To prepare for the ICPC World Finals 2017, your team attended to a training camp. Glauber \"the drinker\" Sokolov was the teacher, and all teams had to answer a form so he would know what topics were the best to teach. The first day was introductory and Glauber said he would just go over well-known topics. He said \"I noticed you all answered that you knew the Knapsack problem very well, so here is a simple exercise about it, follows directly from the definitions. Solve the knapsack problem with repetitions.\".\n\nMore formally, given N types of items, each one with a weight and a cost, choose some items such that the sum of its weights does not exceed S, and the sum of costs is maximum. You may choose any number of items of each type.\n\nSolve Glauber's exercise.\n\nOn the first line two integers N and S, the number of types of items and the maximum allowed weight.\n\nEach of the next N lines has two integers wi and ci, the weight and the cost of the ith type of item.\n\n*Limits* \n\nPrint a single integer, the cost of the items you choose.\n\n"},{"iden":"input","content":"On the first line two integers N and S, the number of types of items and the maximum allowed weight.Each of the next N lines has two integers wi and ci, the weight and the cost of the ith type of item.*Limits*   1 ≤ N, wi ≤ 103  0 ≤ S, ci ≤ 109 "},{"iden":"output","content":"Print a single integer, the cost of the items you choose."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of item types.  \nLet $ S \\in \\mathbb{Z}^+ $ be the maximum allowed weight capacity.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ w_i \\in \\mathbb{Z}^+ $ be the weight and $ c_i \\in \\mathbb{Z}^+ $ be the cost of item type $ i $.\n\nLet $ x_i \\in \\mathbb{Z}_{\\geq 0} $ denote the number of items of type $ i $ selected.\n\n**Constraints**  \n$$\n\\sum_{i=1}^{N} w_i x_i \\leq S\n$$\n\n**Objective**  \nMaximize:  \n$$\n\\sum_{i=1}^{N} c_i x_i\n$$","simple_statement":"Given N types of items, each with a weight and a cost, pick any number of each type so that total weight ≤ S and total cost is maximized. Print the maximum cost.","has_page_source":false}