Boats to Save People

Medium

two-pointersgreedysorting

Each boat carries at most two people, subject to a weight limit. Given everyone's weights, return the minimum number of boats needed to carry every person.

Input

Line 1: space-separated weights
Line 2: the integer limit

Output: the minimum number of boats.

Example 1

Input:

1 2
3

Output:

Example 2

Input:

3 2 2 1
3

Output:

Boats: (1,2), (2), (3).

Example 3

Input:

3 5 3 4
5

Output:

No two fit together.

Constraints

1 ≤ people.length ≤ 5·10^4
1 ≤ people[i] ≤ limit ≤ 3·10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Boats to Save People

Medium

two-pointersgreedysorting

Each boat carries at most two people, subject to a weight limit. Given everyone's weights, return the minimum number of boats needed to carry every person.

Input

Line 1: space-separated weights
Line 2: the integer limit

Output: the minimum number of boats.

Example 1

Input:

1 2
3

Output:

Example 2

Input:

3 2 2 1
3

Output:

Boats: (1,2), (2), (3).

Example 3

Input:

3 5 3 4
5

Output:

No two fit together.

Constraints

1 ≤ people.length ≤ 5·10^4
1 ≤ people[i] ≤ limit ≤ 3·10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.