Overview

First compute the “effective length” of each pipe, then determine which number of pipes \(M\) to select for the best result. The key insight is that selecting pipes in decreasing order of effective length is optimal, and the maximum value can be efficiently computed using sorting + prefix sums.

Analysis

The completed length, given \(M\) selected pipes with a total effective length of \(S\), is \( S - (M-1)K \)

1. First, convert to effective lengths

• Not rusted: \(A_i\)
• Rusted: \(\max(A_i - C, 0)\)

This unifies the “value of each pipe” as an effective length \(v_i\).

---

2. Which set of pipes should we select?

When the number of pipes is fixed at \(M\), the connection cost \((M-1)K\) subtracted is a constant. This means the only thing to maximize is the total effective length \(S\).

Therefore, for a fixed number of pipes \(M\), selecting the top \(M\) pipes by effective length is optimal (by exchange argument).

---

3. Why brute force doesn’t work

Trying all subsets of pipes would require \(2^N\) iterations, which is infeasible (\(N \le 10^5\)). However, due to the property above, it suffices to just “check the top \(M\) pipes for each \(M=1..N\)”.

---

4. How to speed this up

Sort the effective lengths in descending order: \( v_1 \ge v_2 \ge \cdots \ge v_N \) Then the best value when selecting \(M=i\) pipes is \( (v_1+\cdots+v_i) - (i-1)K \) The left-hand sum can be incrementally updated using a prefix sum, so all values of \(i\) can be evaluated in a single pass.

Specifically, in the code: - s: running total of effective lengths from the front - total = s - (i - 1) * K - best = max(best, total)

Finally, if best >= D, output best; otherwise, output -1.

Algorithm

1. Read the input and compute the effective length \(v_i\) for each pipe.
   • If rusted: \(\max(A_i-C,0)\)
   • If not rusted: \(A_i\)
2. Sort the effective length array in descending order.
3. Add one pipe at a time from the front, updating the prefix sum s, and for each count \(i\) compute \( \text{total} = s - (i-1)K \) updating the maximum best.
4. If best >= D, output best; otherwise, output -1.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (effective length array)

Implementation Notes

• Don’t forget max(A-C, 0) to ensure the effective length of a rusted pipe doesn’t go negative.

• Since values can be large (the total can be on the order of \(10^{14}\)), be careful of integer overflow (Python handles this automatically).

• Starting best at 0 is fine (it correctly handles the case where all effective lengths are 0).

  Source Code

import sys

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

    vals = []
    for _ in range(N):
        A, B = map(int, input().split())
        if B == 1:
            v = A - C
            if v < 0:
                v = 0
        else:
            v = A
        vals.append(v)

    vals.sort(reverse=True)

    best = 0
    s = 0
    for i, v in enumerate(vals, 1):  # i = number of selected pipes
        s += v
        total = s - (i - 1) * K
        if total > best:
            best = total

    if best >= D:
        print(best)
    else:
        print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.