No Need

AtCoder

IDarc070_b

Time2000ms

Memory256MB

Difficulty—

AtCoDeer the deer has $N$ cards with positive integers written on them. The number on the $i$\-th card $(1≤i≤N)$ is $a_i$. Because he loves big numbers, he calls a subset of the cards _good_ when the sum of the numbers written on the cards in the subset, is $K$ or greater. Then, for each card $i$, he judges whether it is _unnecessary_ or not, as follows: * If, for any good subset of the cards containing card $i$, the set that can be obtained by eliminating card $i$ from the subset is also good, card $i$ is unnecessary. * Otherwise, card $i$ is NOT unnecessary. Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary. ## Constraints * All input values are integers. * $1≤N≤5000$ * $1≤K≤5000$ * $1≤a_i≤10^9 (1≤i≤N)$ ## Input The input is given from Standard Input in the following format: $N$ $K$ $a_1$ $a_2$ ... $a_N$ ## Partial Score * $300$ points will be awarded for passing the test set satisfying $N,K≤400$. [samples]

Samples

Input #1

3 6
1 4 3

Output #1

1

There are two good sets: {$2,3$} and {$1,2,3$}.
Card $1$ is only contained in {$1,2,3$}, and this set without card $1$, {$2,3$}, is also good. Thus, card $1$ is unnecessary.
For card $2$, a good set {$2,3$} without card $2$, {$3$}, is not good. Thus, card $2$ is NOT unnecessary.
Neither is card $3$ for a similar reason, hence the answer is $1$.

Input #2

5 400
3 1 4 1 5

Output #2

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

Input #3

6 20
10 4 3 10 25 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "No Need",
    "description": {
      "content": "AtCoDeer the deer has $N$ cards with positive integers written on them. The number on the $i$\\-th card $(1≤i≤N)$ is $a_i$. Because he loves big numbers, he calls a subset of the cards _good_ when the ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc070_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "AtCoDeer the deer has $N$ cards with positive integers written on them. The number on the $i$\\-th card $(1≤i≤N)$ is $a_i$. Because he loves big numbers, he calls a subset of the cards _good_ when the ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments