{"raw_statement":[{"iden":"statement","content":"After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.\n\nThis morning, as usual, Petya will come to the market. Petya has _n_ different souvenirs to sell; _i_th souvenir is characterised by its weight _w__i_ and cost _c__i_. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than _m_, and total cost is maximum possible.\n\nHelp Petya to determine maximum possible total cost."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100000, 1 ≤ _m_ ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.\n\nThen _n_ lines follow. _i_th line contains two integers _w__i_ and _c__i_ (1 ≤ _w__i_ ≤ 3, 1 ≤ _c__i_ ≤ 109) — the weight and the cost of _i_th souvenir."},{"iden":"output","content":"Print one number — maximum possible total cost of souvenirs that Petya can carry to the market."},{"iden":"examples","content":"Input\n\n1 1\n2 1\n\nOutput\n\n0\n\nInput\n\n2 2\n1 3\n2 2\n\nOutput\n\n3\n\nInput\n\n4 3\n3 10\n2 7\n2 8\n1 1\n\nOutput\n\n10"}],"translated_statement":[{"iden":"statement","content":"经过几次最近的改革，许多游客计划访问贝兰，贝兰人意识到这是赚钱的机会，纷纷转行以吸引游客。例如，Petya 离开了他之前工作的 IT 公司，开始在集市上售卖纪念品。\n\n今天早上，和往常一样，Petya 将来到集市。Petya 有 #cf_span[n] 件不同的纪念品要卖；第 #cf_span[i] 件纪念品的重量为 #cf_span[wi]，价值为 #cf_span[ci]。Petya 知道他可能无法携带所有纪念品去集市。因此，Petya 希望选择一个纪念品子集，使得其总重量不超过 #cf_span[m]，且总价值尽可能大。\n\n帮助 Petya 确定可能的最大总价值。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 100000], #cf_span[1 ≤ m ≤ 300000]) —— Petya 的纪念品数量和他能携带到集市的总重量限制。\n\n接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[wi] 和 #cf_span[ci] (#cf_span[1 ≤ wi ≤ 3], #cf_span[1 ≤ ci ≤ 109]) —— 第 #cf_span[i] 件纪念品的重量和价值。\n\n请输出一个数字 —— Petya 能携带到集市的纪念品可能的最大总价值。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 100000], #cf_span[1 ≤ m ≤ 300000]) —— Petya 的纪念品数量和他能携带到集市的总重量限制。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[wi] 和 #cf_span[ci] (#cf_span[1 ≤ wi ≤ 3], #cf_span[1 ≤ ci ≤ 109]) —— 第 #cf_span[i] 件纪念品的重量和价值。"},{"iden":"output","content":"请输出一个数字 —— Petya 能携带到集市的纪念品可能的最大总价值。"},{"iden":"examples","content":"输入1 12 1输出0输入2 21 32 2输出3输入4 33 102 72 81 1输出10"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of souvenirs and maximum allowable weight, respectively.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ and $ C = (c_1, c_2, \\dots, c_n) $ be sequences of weights and costs, where $ w_i \\in \\{1,2,3\\} $ and $ c_i \\in \\mathbb{Z}^+ $ for all $ i \\in \\{1, \\dots, n\\} $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100000 $  \n2. $ 1 \\leq m \\leq 300000 $  \n3. $ 1 \\leq w_i \\leq 3 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\leq c_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFind a subset $ S \\subseteq \\{1, \\dots, n\\} $ such that:  \n$$\n\\sum_{i \\in S} w_i \\leq m\n$$  \nand the total cost  \n$$\n\\sum_{i \\in S} c_i\n$$  \nis maximized.","simple_statement":null,"has_page_source":false}