Reindeer and Sleigh 2

AtCoder

IDabc437_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ reindeer and one sled. The $i$\-th reindeer has weight $W_i$ and strength $P_i$. For each reindeer, choose either "pull the sled" or "ride on the sled". Here, the total strength of the reindeer pulling the sled must be greater than or equal to the total weight of the reindeer riding on the sled. What is the maximum number of reindeer that can ride on the sled? You are given $T$ test cases. Solve each of them. ## Constraints * $1\leq T\leq 10^5$ * $1\leq N\leq 3\times 10^5$ * $1\leq W_i,P_i\leq 10^9$ * All input values are integers. * The sum of $N$ in one input file is at most $3\times 10^5$. ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ Each test case is given in the following format: $N$ $W_1$ $P_1$ $W_2$ $P_2$ $\vdots$ $W_N$ $P_N$ [samples]

Samples

Input #1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

Output #1

2
0
6

For the 1st test case, if the 3rd reindeer pulls the sled and the 1st and 2nd reindeer ride on the sled, the total strength of the reindeer pulling the sled is $P_3=9$, and the total weight of the reindeer riding on the sled is $W_1+W_2=7$, satisfying the condition. Since not all reindeer can ride on the sled, the answer is $2$.

API Response (JSON)

{
  "problem": {
    "name": "Reindeer and Sleigh 2",
    "description": {
      "content": "There are $N$ reindeer and one sled. The $i$\\-th reindeer has weight $W_i$ and strength $P_i$. For each reindeer, choose either \"pull the sled\" or \"ride on the sled\". Here, the total strength of the r",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc437_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ reindeer and one sled. The $i$\\-th reindeer has weight $W_i$ and strength $P_i$.\nFor each reindeer, choose either \"pull the sled\" or \"ride on the sled\". Here, the total strength of the r...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments