Alex is in a shop that sells N products. You are given an array A of N positive integers, indexed from 0 to N-1. A[K] represents the price of the K-th product.

Alex can spend at most B in total. He wants to buy as many products as possible. He can buy each product at most once, and the total price of all purchased products must be less than or equal to B.

Function

int solution(int B, vector<int> &A);

Given an integer B and an array A of N integers, return the maximum number of products Alex can buy without exceeding his budget.

Examples

Example 1

Input:

B = 40
A = [9, 16, 4]

Output:

3

Explanation:

Alex can buy all three products:

9 + 16 + 4 = 29 ≤ 40

Therefore, the maximum number of products is 3.

---

Example 2

Input:

B = 8
A = [3, 4, 2, 3, 1]

Output:

3

Explanation:

Alex can buy the products with prices:

3 + 3 + 1 = 7 ≤ 8

Therefore, the maximum number of products is 3.

---

Example 3

Input:

B = 500
A = [1000, 2000]

Output:

0

Explanation:

The cheapest product costs 1000, which is already greater than the available budget of 500.

Therefore, Alex cannot buy any product.

Constraints

• N is an integer within the range [2..100,000].
• B is an integer within the range [1..2,000,000,000].
• Each element of array A is an integer within the range [1..1,000,000,000].