[GDCPC 2023] New Houses

Luogu

IDLGP9693

Time1000ms

Memory1024MB

DifficultyP3

2023广东O2优化省赛/邀请赛

With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses which are arranged in a row. The houses are numbered from $1$ to $m$ (both inclusive). House $u$ and $v$ are neighboring houses, if and only if $|u-v|=1$. We need to assign each person to a house so that no two people will move into the same house. If two people move into a pair of neighboring houses, they will become neighbors of each other. Some people like to have neighbors while some don't. For the $i$-th person, if he has at least one neighbor, his happiness will be $a_i$; Otherwise if he does not have any neighbor, his happiness will be $b_i$. As the planner of this community, you need to maximize the total happiness. ## Input There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n \le 5 \times 10^5$, $1 \le m \le 10^9$, $n \le m$) indicating the number of people and the number of houses. For the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) indicating the happiness of the $i$-th person with and without neighbors. It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$. ## Output For each test case output one line containing one integer indicating the maximum total happiness. [samples] ## Note For the first sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ to $4$ move into house $3$ to $5$. Thus, person $1$ have no neighbors while person $2$ to $4$ have neighbors. The answer is $100 + 100 + 100 + 100 = 400$. Of course, we can also let person $2$ to $4$ move into house $1$ to $3$ and let person $1$ move into house $5$. This will also give us $400$ total happiness. For the second sample test case, as there are only $2$ houses, person $1$ and $2$ have to be neighbors. The answer is $1 + 1 = 2$. For the third sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ move into house $3$. Thus, both of them have no neighbors. The answer is $50 + 1000 = 1050$.

Samples

Input #1

Output #1

400
2
1050

API Response (JSON)

{
  "problem": {
    "name": "[GDCPC 2023] New Houses",
    "description": {
      "content": "With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9693"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments