During a flood, rescue boats take people to safety. The array people holds the weight of each person. There are unlimited boats, and every boat can carry at most limit weight in total. A boat carries at most two people at a time, and only if their weights add up to limit or less.
Return the smallest number of boats needed to carry everyone.
Examples
Example 1:
Input: people = [2,5,3,4], limit = 6
Output: 3
Explanation: One way: (2 and 4), (3) and (5). The person with weight 5 cannot share a boat with anyone.
Example 2:
Input: people = [1,2,2,3], limit = 4
Output: 2
Explanation: Two boats: (1 and 3) and (2 and 2).
Example 3:
Input: people = [5,5,5], limit = 5
Output: 3
Explanation: Nobody can share, so each person needs a boat.