711. Boats to Save People

0

Medium

Given an array of people's weights and a limit for each boat, determine the minimum number of boats required to carry all the people. Each boat can carry a maximum weight equal to the limit and can accommodate at most two people whose combined weight does not exceed the limit.

Input Format

The input starts with an integer N, denoting the size of the array. The next line contains N space-separated integers representing the weights of the people. Finally, a single integer is provided as the limit.

Output Format

The output is a single integer representing the minimum number of boats required to carry all the people.

Example

Input

4
3 5 3 4
5

Output

4

Constraints

- 1 <= people.length <= 5 * 10

^{4}- 1 <= people[i] <= limit <= 3 * 10^{4}Loading...

View Submissions

Console