Minimizing River Crossing Trips

You are given N people with individual weights and a boat that can carry at most C kilograms per trip. Your task is to determine the minimum number of trips required to transport all the people across the river.

The boat can carry at most two people at a time, and the sum of their weights must not exceed C. It is always optimal to pair the lightest person who can safely share the boat with the heaviest person available. If they cannot be paired, the heaviest person crosses alone.

Note: The solution is based on a greedy strategy using two pointers after sorting the weights. The mathematical formulation for pairing the persons is given by:

\[ \text{if } w_{left} + w_{right} \leq C \text{ then pair them; otherwise, move } w_{right} \text{ alone.} \]

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains two integers N and C, where N is the number of people and C is the maximum capacity of the boat in kilograms.
• The second line contains N integers separated by spaces, representing the weights of the people.

outputFormat

Output a single integer to standard output (stdout) that represents the minimum number of trips required to transport all the people across the river.

4 100
60 70 30 40

2