###### 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
내가 제출한 코드가 왜 틀렸는지 프로그래머스 AI에게 물어보세요.
제출 후 채점하기를 눌러 30점 이상인 경우 물어볼 수 있어요.
베타 기간 동안에는 한 문제당 1번만 물어볼 수 있어요.