H - Self-Replacing Cake (Hard)

注意

この問題は、D1 問題と設定が酷似している一方、問題文の一部が異なります。
問題文中の異なる点は太字で示していますが、制約に対しては行なっていません。

問題

あなたは、$N$ 個のケーキのコレクションを持っています。それぞれは見た目や大きさが多種多様であり、重さや長さも様々です。
具体的には、$i$ 番目のケーキの大きさは $S_i$ です。
ところで、あなたは今ある組織に命を狙われています。
いまから、$D$ 日間の猶予が与えられます。その間に、組織に可能な限り貢献することで、絶命を免れることができる可能性があります。

組織への貢献として認められるものは、以下のとおりです。

• ケーキを完食する

1日毎に、以下の操作がこの順に繰り返し行われます。

• 食事：ケーキのサイズの合計があなたの胃の大きさ $K$ 以下となるようなケーキを好きな個数選び、ケーキを食べる
• 増殖：まだ一度も完食されていないケーキについて、サイズが 2倍 になる

あなたが食べることのできるケーキの個数の最大値を出力してください。

制約

• $1\leq N\leq 2\times 10^5$
• $1\leq D, K\leq 10^{18}$
• $1\leq S_i\leq 10^{18}$
• 入力はすべて整数

入力

$N~D~K$

$S_1~S_2~\cdots~S_{N-1}~S_N$

入力例1

5 5 5
1 2 3 4 5
Copy

出力例1

3
Copy

例えば、以下のような流れでこの回数が達成可能です。

• 1日目、すべてのケーキのサイズは $\{1, 2, 3, 4, 5\}$ です。3つ目のケーキを食べます。
• 2日目、すべてのケーキのサイズは $\{2, 4, 8, 10\}$ です。2つ目のケーキを食べます。
• 3日目、すべてのケーキのサイズは $\{4, 16, 20\}$ です。1つ目のケーキを食べます。
• 4日目、すべてのケーキのサイズは $\{32, 40\}$ です。ケーキを食べることは出来ません。
• 5日目、すべてのケーキのサイズは $\{64, 80\}$ です。ケーキを食べることは出来ません。

入力例2

5 5 5
1 1 1 1 1
Copy

出力例2

5
Copy

入力例3

8 9 100
1 2 3 4 5 6 7 8
Copy

出力例3

8
Copy