Minimum Total Bridge Crossing Time for Convoy

A convoy of armored vehicles is lined up on a single‐lane street waiting to cross a one‐lane bridge. The bridge, which is located over a river, has a maximum load capacity. To manage the traffic, the convoy is divided into groups, with each group crossing simultaneously. However, the total weight of the vehicles in any group cannot exceed the bridge's maximum load capacity.

Each vehicle is characterized by its weight and the time it takes to cross the bridge at its fastest speed. When a group of vehicles crosses the bridge together, every vehicle uses its fastest speed; therefore, the time taken by the group is determined by the slowest (i.e. the vehicle with the maximum crossing time) in that group. The vehicles must maintain their order because overtaking is not allowed.

The task is to partition the given list of vehicles into consecutive groups such that (1) the sum of weights in each group does not exceed the bridge's capacity, and (2) the total crossing time (which is the sum of the crossing times of all groups) is minimized.

Formally, if there are N vehicles, and each vehicle i has weight w_i and crossing time t_i, you are given a maximum allowable total weight C for any group. You must determine a partition (i.e. group the vehicles in order) so that for each group, the sum of weights is at most C, and the time for that group is the maximum crossing time among the vehicles in that group. The objective is to minimize the sum of these group crossing times over all groups.

Note on formulas:

If we let dp[i] denote the minimum total time to get the first i vehicles across, then:

\(dp[i] = \min_{j=1}^{i} \{ dp[j-1] + \max_{k=j}^{i}(t_k) \}\)

subject to \(\sum_{k=j}^{i}w_k \leq C\).

inputFormat

The first line contains two integers: N (the number of vehicles) and C (the maximum load capacity of the bridge).

Then follow N lines, each containing two integers: w_i and t_i, representing the weight and crossing time of the i-th vehicle, respectively.

outputFormat

Output a single integer — the minimum total time required for all vehicles to cross the bridge.

sample

3 10
2 5
4 2
4 3

8