問題文

AtCoder Land には N 個のアトラクションがあります。
i 番目のアトラクションには、以下の 2 通りの搭乗方法があります。

• 通常通り搭乗する。
  • A_i 分後に搭乗が終了する。
• ファストパスを使って搭乗する。
  • B_i 分後に搭乗が終了する。このとき、ファストパスが 1 枚消費される。

あなたはファストパスを K 枚持っています。
同じアトラクションに複数回搭乗しないものとすると、 T 分後までに最大でいくつのアトラクションに搭乗できますか？
但し、アトラクションを乗り換える時間は無視できること、最後に搭乗するアトラクションについて T 分後までに搭乗が終了している必要があることに注意してください。

制約

• 入力は全て整数
• 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}

入力例 1

5 2 20
7 4
10 8
3 3
8 7
9 5

出力例 1

4

この入力において AtCoder Land には 5 個のアトラクションがあり、あなたはファストパスを 2 枚持っています。

• まず、 5 番目のアトラクションにファストパスを使って搭乗する。
  • このとき、 5 分後に搭乗が終了し、ファストパスの残りは 1 枚になります。 全体で 5 分経過しています。
• 次に、 3 番目のアトラクションに通常通り搭乗する。
  • このとき、 3 分後に搭乗が終了します。 全体で 8 分経過しています。
• 次に、 1 番目のアトラクションにファストパスを使って搭乗する。
  • このとき、 4 分後に搭乗が終了し、ファストパスの残りは 0 枚になります。 全体で 12 分経過しています。
• 最後に、 4 番目のアトラクションに通常通り搭乗する。
  • このとき、 8 分後に搭乗が終了します。 全体で 20 分経過しています。

以上の通りにすると 4 つのアトラクションに搭乗でき、これが最大であることが証明できます。

入力例 2

5 5 1
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000

出力例 2

0

T 分以内にひとつもアトラクションに搭乗できない場合もあります。

入力例 3

5 5 1000000000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000
1000000000000 1000000000000

出力例 3

5

T 分以内に全てのアトラクションに搭乗できる場合もあります。

入力例 4

15 4 60
9 4
8 8
10 10
7 6
10 3
6 6
8 7
9 5
6 5
4 2
1 1
7 6
8 6
6 4
4 3

出力例 4

12