59. Hot Air Balloon Capacity

Difficulty: easy · Greedy, Sorting

Problem

A hot air balloon can carry at most `maxWeight` kilograms. Given the weights of the people waiting, find the maximum **number** of people who can ride together without the total weight exceeding `maxWeight`.

Input

- Line 1: the weights of the people, separated by spaces. - Line 2: the integer `maxWeight`.

Output

Print the maximum number of people.

Example 1

Input:
20 30 40 50
100
Output:
3

Explanation: The three lightest people weigh 20+30+40 = 90 <= 100; adding 50 would exceed the limit.

Example 2

Input:
60 70
50
Output:
0

Explanation: Even the lightest person (60) is too heavy, so no one can ride.

Constraints

- 1 <= number of people <= 10^5 - 1 <= each weight <= 10^4 - 1 <= maxWeight <= 10^9

Solutions are judged against 2 sample and 8 hidden tests. Sign in to solve it · All problems