Bridge Crossing Optimization

An old bridge cannot support an excessive load; hence, at any moment, the total weight of the people on the bridge cannot exceed a given limit. A team of people, each with a specific crossing time and weight, needs to cross the bridge in batches. In each batch, the crossing time is determined by the slowest person in that group. The batches must be formed sequentially (i.e. the team is partitioned in the given order) so that one batch crosses completely before the next batch starts. The objective is to determine a way to partition the team into groups such that the total crossing time is minimized.

More formally, you are given an integer W representing the maximum weight the bridge can support at any time, and an integer n representing the number of people in the team. Each of the following n lines contains two integers: t_i (the time it takes for person i to cross the bridge) and w_i (the weight of person i).

You need to partition the team (preserving the order) into one or more consecutive groups such that the total weight in each group does not exceed W. The time required for a group is equal to the maximum t_i among the people in that group, and the total time is the sum of the times for each group. Your task is to compute the minimum total time required for all team members to cross the bridge.

The optimization can be formulated using dynamic programming. Let \(dp[i]\) be the minimum total crossing time for the first \(i\) individuals. Then, for every possible partition, update \(dp[i]\) as follows:

[ dp[i] = \min_{0 \leq j < i \text{ and } \sum_{k=j+1}^{i} w_k \leq W} { dp[j] + \max_{k=j+1}^{i} t_k } ]

inputFormat

The first line contains two integers (n) and (W) (1 ≤ (n) ≤ 10⁵, 1 ≤ (W) ≤ 10⁹), where (n) is the number of people and (W) is the maximum weight capacity of the bridge. Each of the following (n) lines contains two integers (t_i) and (w_i) (1 ≤ (t_i),(w_i) ≤ 10⁹), representing the time required for the (i)-th person to cross and their weight, respectively.

outputFormat

Output a single integer: the minimum total time required for all team members to cross the bridge.

sample

4 10
5 4
3 5
6 2
8 8

19