{"problem":{"name":"Jewel Pairs","description":{"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$. A pair of two gems $(i,j)$ is said to be a **good** ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"wtf22_day2_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"wtf22_day2_c","tags":[],"sample_group":[["4 5\n1 2\n1 3\n2 1\n2 4","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)$."],["5 10\n3 8\n4 2\n1 5\n1 3\n1 2","17\n\nIn this case, it is optimal to make the pairs $(1,5)$ and $(2,3)$."],["9 10\n8 2\n7 10\n1 4\n3 0\n5 3\n3 6\n2 5\n5 9\n5 4","34"],["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","4704511147"]],"created_at":"2026-03-03 11:01:14"}}