概要

各パイプの「有効長」を先に求めると、完成後の長さは
\(K + \sum (e_i - K)\) と書き直せます。
この形にすると、各パイプを選ぶべきかどうかが独立に判断でき、\(O(N)\) で最大値を求められます。

考察

まず、各パイプの有効長 \(e_i\) を考えます。

• 錆びていないなら \(e_i = A_i\)
• 錆びているなら \(e_i = \max(A_i - C, 0)\)

完成品の長さは、\(M\) 本選んだとき

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

です。

ここで式を少し変形すると、

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

となります。
この変形がこの問題の一番大事なポイントです。

何が嬉しいのか？

この式では、空でない集合を 1 つ選んだときの長さが

• 基本値として \(K\)
• 各パイプを選ぶと \(e_i - K\) だけ増減する

と見られます。

つまり、各パイプは

• \(e_i - K > 0\) なら選ぶと得
• \(e_i - K < 0\) なら選ぶと損
• \(e_i - K = 0\) なら選んでも選ばなくても同じ

です。

したがって、

• \(e_i > K\) のパイプは全部選ぶのが得
• \(e_i < K\) のパイプは選ばない方がよい
• \(e_i = K\) のパイプはどちらでもよい

と分かります。

例

例えば、有効長が \([10, 8, 4]\)、\(K = 5\) のとき、

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

です。

• 1 本目は選ぶと \(+5\)
• 2 本目は選ぶと \(+3\)
• 3 本目は選ぶと \(-1\)

なので、1 本目と 2 本目だけ選ぶのが最適です。

実際、長さは

\[ 10 + 8 - 5 = 13 \]

で最大になります。

---

素朴な方法ではなぜだめか？

全部分集合を試すと、選び方は \(2^N\) 通りあります。
\(N \le 10^5\) なので、これは当然間に合いません。

しかし上の変形を使えば、「各パイプを独立に見て、得なら足す」とできるので、1 回の走査で答えが出せます。

---

ただし 1 点注意

「1 本以上選ばなければならない」条件があります。

もし \(e_i > K\) のパイプが 1 本もないとすると、どのパイプも選んでも得しません。
このとき複数本選ぶ意味はなく、有効長が最大の 1 本だけ選ぶのが最適です。

つまり場合分けは次の通りです。

• \(e_i > K\) のパイプが 1 本以上ある
  \(\Rightarrow\) それらを全部選ぶ
• 1 本もない
  \(\Rightarrow\) 有効長最大の 1 本だけ選ぶ

アルゴリズム

1. 各パイプについて有効長 \(e_i\) を求める。
2. 同時に以下を管理する。
   • max_e: 有効長の最大値
   • total_pos: \(e_i > K\) のものについて \((e_i - K)\) の合計
3. 最適値 best を次のように決める。
   • total_pos > 0 なら
     $\( \text{best} = K + \text{total\_pos} \)$
   • そうでなければ
     $\( \text{best} = \max e_i \)$
4. best >= D なら best を、そうでなければ -1 を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 錆びたパイプの有効長は \(\max(A_i - C, 0)\) で、負にならないようにします。

• total_pos は「\(e_i > K\) のときだけ」加算します。
  \(e_i = K\) のものは寄与が \(0\) なので、入れても入れなくても答えは同じです。

• 合計値は大きくなるので、C++ なら long long が必要です。Python ではそのままで大丈夫です。

  ソースコード

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()

---

この解説は gpt-5.4-high によって生成されました。