Description

S company investigated the amount of money required to purchase items by the department to provide the necessary supplies for each department. But, buying all items is impossible due to the limit of the budget. Hence, the company tries to purchase items for as many departments as possible.

When buying items, the whole amount of money requested by the department should be provided. For example, for the department who requested 1,000 , the exact 1,000 should be provided, and less than 1,000 cannot be provided.

Given an array of requested money d and budget budget as a parameter, write a function solution to return the maximum number of departments that can be supplied.

Constraints
  • d is an array of money requested by each department, and its length (the number of all departments) is between 1 and 100.
  • Each element of d indicates money requested by each department, and requested money is a natural number less than 100,000.
  • budget represents the budget and is a natural number less than 10,000,000.
Examples
d budget result
[1,3,2,5,4] 9 3
[2,2,3,3] 10 4

Example #1

Each department requested money as [1, 3, 2, 5, 4]. To purchase items of departments that requested 1, 2, and 4, 7 out of budget 9 is consumed and only 2 has remained. Since the exact whole money requested by the department should be provided, the remaining 2 is insufficient to support other departments. Other than the above way, the ways to support the three departments are as follows.

  • To purchase items of departments which requested 1, 2, and 3, 6 is required.
  • To purchase items of departments which requested 1, 2, and 5, 8 is required.
  • To purchase items of departments which requested 1, 3, and 4, 8 is required.
  • To purchase items of departments which requested 1, 3, and 5, 9 is required.

Since there is no way to purchase items of more than three departments, the maximum number of departments that can be supported is three.

Example #2
To purchase items of all departments, 10 is required. Hence, a maximum of four departments can be supported.

Result Stop
Result of [Run] or [Submit] will be displayed here