{"raw_statement":[{"iden":"problem statement","content":"There are $N$ gems numbered $1$ to $N$. Gem $i$ has a color $C_i$ and a value $V_i$. Here, colors are represented as integers from $1$ through $N$.\nA pair of two gems $(i,j)$ is said to be a **good** pair if (and only if) they satisfy the following conditions:\n\n*   $C_i \\neq C_j$,\n*   $V_i + V_j \\leq L$.\n\nYou will make some number of good pairs from the $N$ gems. A gem must not belong to multiple pairs, but it is fine if some gems belong to no pairs.\nFind the maximum possible total value of all gems in your pairs."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 250000$\n*   $1 \\leq L \\leq 10^9$\n*   $1 \\leq C_i \\leq N$\n*   $0 \\leq V_i \\leq L$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $L$\n$C_1$ $V_1$\n$C_2$ $V_2$\n$\\vdots$\n$C_N$ $V_N$"},{"iden":"sample input 1","content":"4 5\n1 2\n1 3\n2 1\n2 4"},{"iden":"sample output 1","content":"4\n\nThe pair $(1,2)$ is not good because the first condition is not satisfied.\nThe pair $(1,4)$ is not good because the second condition is not satisfied.\nIn this case, it is optimal to make the pair $(2,3)$."},{"iden":"sample input 2","content":"5 10\n3 8\n4 2\n1 5\n1 3\n1 2"},{"iden":"sample output 2","content":"17\n\nIn this case, it is optimal to make the pairs $(1,5)$ and $(2,3)$."},{"iden":"sample input 3","content":"9 10\n8 2\n7 10\n1 4\n3 0\n5 3\n3 6\n2 5\n5 9\n5 4"},{"iden":"sample output 3","content":"34"},{"iden":"sample input 4","content":"20 1000000000\n15 239276621\n15 910500852\n15 245532750\n15 715892722\n16 80707349\n15 257261830\n12 950300098\n15 322288793\n15 256358887\n15 504976376\n2 907119713\n15 152036484\n13 298766520\n15 480968804\n15 285187325\n13 755031424\n15 69837029\n15 88860861\n9 596982638\n15 272961035"},{"iden":"sample output 4","content":"4704511147"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}