AT_codequeen2024_final_h Good bye, AtCoder Land.

AtCoder Land には $ N $ 個のアトラクションがあります。 $ i $ 番目のアトラクションには、以下の $ 2 $ 通りの搭乗方法があります。 - 通常通り搭乗する。 - $ A_i $ 分後に搭乗が終了する。 - ファストパスを使って搭乗する。 - $ B_i $ 分後に搭乗が終了する。このとき、ファストパスが $ 1 $ 枚消費される。 あなたはファストパスを $ K $ 枚持っています。 同じアトラクションに複数回搭乗しないものとすると、 $ T $ 分後までに最大でいくつのアトラクションに搭乗できますか？ 但し、アトラクションを乗り換える時間は無視できること、最後に搭乗するアトラクションについて $ T $ 分後までに搭乗が終了している必要があることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ T $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

答えを整数として出力せよ。

### Sample Explanation 1 この入力において AtCoder Land には $ 5 $ 個のアトラクションがあり、あなたはファストパスを $ 2 $ 枚持っています。 - まず、 $ 5 $ 番目のアトラクションにファストパスを使って搭乗する。 - このとき、 $ 5 $ 分後に搭乗が終了し、ファストパスの残りは $ 1 $ 枚になります。 全体で $ 5 $ 分経過しています。 - 次に、 $ 3 $ 番目のアトラクションに通常通り搭乗する。 - このとき、 $ 3 $ 分後に搭乗が終了します。 全体で $ 8 $ 分経過しています。 - 次に、 $ 1 $ 番目のアトラクションにファストパスを使って搭乗する。 - このとき、 $ 4 $ 分後に搭乗が終了し、ファストパスの残りは $ 0 $ 枚になります。 全体で $ 12 $ 分経過しています。 - 最後に、 $ 4 $ 番目のアトラクションに通常通り搭乗する。 - このとき、 $ 8 $ 分後に搭乗が終了します。 全体で $ 20 $ 分経過しています。 以上の通りにすると $ 4 $ つのアトラクションに搭乗でき、これが最大であることが証明できます。 ### Sample Explanation 2 $ T $ 分以内にひとつもアトラクションに搭乗できない場合もあります。 ### Sample Explanation 3 $ T $ 分以内に全てのアトラクションに搭乗できる場合もあります。 ### Constraints - 入力は全て整数 - $ 1 \le K \le N \le 2 \times 10^5 $ - $ 1 \le T \le 10^{18} $ - $ 1 \le B_i \le A_i \le 10^{12} $