#878 linoは同意を得たい

問題文

問題文の言語

linoとOsaragiは、学校祭について住民の同意を得るために家々を訪問する。

訪問する家には順番に $1$ から $N$ までの番号が付いており、訪問順序を変更することはできない。

$i$ 番目の家で同意を得るには $a_i$ 分かかる。

通常の1日に訪問に使える時間は最大 $K$ 分である。ただし、丸1日休むと、その直後の日に限り最大 $2K$ 分を使える。増えた時間をさらに翌日へ持ち越すことはできない。

1日に訪問する家は、指定された訪問順序において連続する区間でなければならない。1軒の家で同意を得る作業を複数の日に分割することはできない。

$1$ 番目から $N$ 番目までのすべての家で順番に同意を得るために必要な最小日数を求めよ。休んだ日も日数に含める。

入力は次の形式で与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、すべての家で同意を得るために必要な最小日数を1行に出力せよ。

例 1

入力例

1
3 3
2 2 2

出力例

2

1日目に休み、2日目に $6$ 分を使えば、3軒すべてを訪問できる。

例 2

入力例

1
4 5
2 3 4 1

出力例

2

1日目に1番目と2番目の家を訪問し、2日目に3番目と4番目の家を訪問できる。

例 3

入力例

1
1 600
600

出力例

1

家は1軒だけなので、1日で訪問できる。

例 4

入力例

出力例

2
2
1

前の3つの例を1つの入力にまとめたものである。各ケースの答えを1行ずつ出力する。