Fewest Lifeboats

A ferry is running a safety drill. weights[i] is the weight of passenger i in kilograms. Each lifeboat carries at most two passengers, and the total weight in a boat must not be more than limit. Every passenger weighs at most limit, so everyone fits in a boat on their own.

Write fewest_boats(weights, limit) that returns the smallest number of boats that carry everyone.

Examples

fewest_boats([70, 50, 80, 50], 100)   # returns 3
fewest_boats([40, 60, 30, 70], 100)   # returns 2
fewest_boats([90, 90, 90], 100)       # returns 3

In the first example the two passengers weighing 50 share a boat, and the other two go alone.

Constraints

• 0 <= len(weights) <= 100,000
• 1 <= weights[i] <= limit <= 10^6