Examination

AtCoder

IDarc147_e

Time2000ms

Memory256MB

Difficulty—

$N$ students, numbered $1,2,\ldots,N$, took an examination. Student $i\,(1 \leq i \leq N)$ had to score at least $B_i$ points to graduate, where they actually scored $A_i$ points. You can repeat the following operation any number of times (possibly zero): * Choose two students, and swap their scores. Your goal is to make everyone graduate. Determine whether it is possible. If it is possible, find the maximum number of students whose scores do not change during the process. ## Constraints * $2 \leq N \leq 3 \times 10^5$ * $1 \leq A_i,B_i \leq 10^9\,(1 \leq i \leq N)$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$ [samples]

Samples

Input #1

Output #1

1

If you swap scores of Student $1$ and $2$, everyone can graduate. Here, the number of students whose scores do not change is $1$ (only Student $3$).

Input #2

2
100 1
100 1

Output #2

Input #3

Output #3

\-1

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Examination",
    "description": {
      "content": "$N$ students, numbered $1,2,\\ldots,N$, took an examination. Student $i\\,(1 \\leq i \\leq N)$ had to score at least $B_i$ points to graduate, where they actually scored $A_i$ points. You can repeat the f",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc147_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$N$ students, numbered $1,2,\\ldots,N$, took an examination. Student $i\\,(1 \\leq i \\leq N)$ had to score at least $B_i$ points to graduate, where they actually scored $A_i$ points.\nYou can repeat the f...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments