Sake or Water

AtCoder

IDabc441_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ cups, each containing a colorless and transparent liquid. Specifically, the $i$\-th $(1\leq i\leq N)$ cup contains $A_i$ ml of liquid. It is known that exactly $K$ of these cups contain sake (rice wine), and the rest contain water. However, it is not known which cups contain sake. Takahashi can choose some (one or more) cups and drink all the liquid in them. Find the minimum number of cups he needs to choose to ensure he drinks at least $X$ ml of sake, regardless of which cups contain sake. If such a choice is impossible, print $-1$. ## Constraints * $1 \leq K \leq N \leq 3\times 10^5$ * $1 \leq A_i \leq 10^9$ * $1 \leq X \leq 3\times 10^{14}$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ $X$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

3 2 5
10 6 8

Output #1

2

Consider the case where Takahashi chooses the first and third cups and drinks them.
Two out of the three cups contain sake, so the following three cases are possible:

*   If the first and second cups contain sake

He drinks $10$ ml of sake and $8$ ml of water.

*   If the first and third cups contain sake

He drinks $18$ ml of sake.

*   If the second and third cups contain sake

He drinks $8$ ml of sake and $10$ ml of water.
Thus, in all cases, he can drink at least $5$ ml of sake.  
On the other hand, it is impossible to satisfy the condition by choosing only one cup without knowing which cups contain sake.
Therefore, print $2$.

Input #2

2 1 8
6 10

Output #2

\-1

If the first cup contained sake, it is impossible to drink $8$ ml or more of sake no matter which cups are chosen.  
Therefore, print $-1$.

Input #3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Sake or Water",
    "description": {
      "content": "There are $N$ cups, each containing a colorless and transparent liquid.   Specifically, the $i$\\-th $(1\\leq i\\leq N)$ cup contains $A_i$ ml of liquid.   It is known that exactly $K$ of these cups cont",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc441_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ cups, each containing a colorless and transparent liquid.  \nSpecifically, the $i$\\-th $(1\\leq i\\leq N)$ cup contains $A_i$ ml of liquid.  \nIt is known that exactly $K$ of these cups cont...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments