Overview

If we first compute the “effective length” of each pipe, the final length can be rewritten as
\(K + \sum (e_i - K)\).
With this formulation, whether to select each pipe can be decided independently, and the maximum value can be found in \(O(N)\).

Analysis

First, consider the effective length \(e_i\) of each pipe.

• If not rusted: \(e_i = A_i\)
• If rusted: \(e_i = \max(A_i - C, 0)\)

When \(M\) pipes are selected, the length of the finished product is

\[ \left(\sum e_i\right) - (M - 1)K \]

Now, with a slight rearrangement,

\[ \left(\sum e_i\right) - (M - 1)K = K + \sum (e_i - K) \]

This rearrangement is the most important insight of this problem.

Why is this useful?

In this formula, the length when selecting a non-empty subset can be viewed as:

• A base value of \(K\)
• Each pipe, when selected, contributes an increase or decrease of \(e_i - K\)

In other words, for each pipe:

• If \(e_i - K > 0\), selecting it is beneficial
• If \(e_i - K < 0\), selecting it is detrimental
• If \(e_i - K = 0\), selecting it makes no difference

Therefore:

• Pipes with \(e_i > K\) should all be selected
• Pipes with \(e_i < K\) should not be selected
• Pipes with \(e_i = K\) can go either way

Example

For instance, if the effective lengths are \([10, 8, 4]\) and \(K = 5\), then

\[ e_i - K = [5, 3, -1] \]

• Selecting the 1st pipe gives \(+5\)
• Selecting the 2nd pipe gives \(+3\)
• Selecting the 3rd pipe gives \(-1\)

So selecting only the 1st and 2nd pipes is optimal.

Indeed, the length is

\[ 10 + 8 - 5 = 13 \]

which is the maximum.

---

Why doesn’t a brute-force approach work?

Trying all subsets gives \(2^N\) possibilities.
Since \(N \le 10^5\), this is clearly too slow.

However, using the above rearrangement, we can “look at each pipe independently and add it if beneficial,” so the answer can be computed in a single pass.

---

One caveat

There is the condition that “at least one pipe must be selected.”

If there are no pipes with \(e_i > K\), then selecting any pipe is not beneficial.
In this case, there is no point in selecting multiple pipes, and selecting only the single pipe with the maximum effective length is optimal.

The case analysis is as follows:

• If there is at least one pipe with \(e_i > K\)
  \(\Rightarrow\) Select all such pipes
• If there are none
  \(\Rightarrow\) Select only the single pipe with the maximum effective length

Algorithm

1. Compute the effective length \(e_i\) for each pipe.
2. Simultaneously maintain the following:
   • max_e: the maximum effective length
   • total_pos: the sum of \((e_i - K)\) for all pipes where \(e_i > K\)
3. Determine the optimal value best as follows:
   • If total_pos > 0:
     $\( \text{best} = K + \text{total\_pos} \)$
   • Otherwise:
     $\( \text{best} = \max e_i \)$
4. If best >= D, output best; otherwise, output -1.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• The effective length of a rusted pipe is \(\max(A_i - C, 0)\), ensuring it does not become negative.

• total_pos is accumulated “only when \(e_i > K\).”
  Pipes with \(e_i = K\) contribute \(0\), so including or excluding them does not affect the answer.

• The total can become large, so in C++ you need long long. In Python, this is handled automatically.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, D, K, C = map(int, input().split())

    total_pos = 0
    max_e = 0

    for _ in range(N):
        A, B = map(int, input().split())
        e = A if B == 0 else max(A - C, 0)
        if e > max_e:
            max_e = e
        if e > K:
            total_pos += e - K

    best = K + total_pos if total_pos > 0 else max_e
    print(best if best >= D else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.