Jewel Pairs

AtCoder

IDwtf22_day2_c

Time2000ms

Memory256MB

Difficulty—

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** pair if (and only if) they satisfy the following conditions: * $C_i \neq C_j$, * $V_i + V_j \leq L$. You 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. Find the maximum possible total value of all gems in your pairs. ## Constraints * $1 \leq N \leq 250000$ * $1 \leq L \leq 10^9$ * $1 \leq C_i \leq N$ * $0 \leq V_i \leq L$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $L$ $C_1$ $V_1$ $C_2$ $V_2$ $\vdots$ $C_N$ $V_N$ [samples]

Samples

Input #1

Output #1

4

The pair $(1,2)$ is not good because the first condition is not satisfied.
The pair $(1,4)$ is not good because the second condition is not satisfied.
In this case, it is optimal to make the pair $(2,3)$.

Input #2

Output #2

17

In this case, it is optimal to make the pairs $(1,5)$ and $(2,3)$.

Input #3

Output #3

Input #4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

Output #4

4704511147

API Response (JSON)

{
  "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** ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments