皇帝は秤で文書の重さを量り、昼夜に処理する分量を定め、それを満たすまでは休めなかった。
- 司馬遷『史記』「秦始皇本紀」
秦の始皇帝は、自ら定めた分量の文書を処理するまで休まなかったといいます。あなたはそのそばで、皇帝の指示を竹簡に書き留める史官です。皇帝が休めないということは、あなたも休めないということです。
皇帝は、過去 日間に出した指示を本にまとめるよう命じました。竹簡とは文字を書くための竹の札で、複数の札を順番にひもでつなぐと 1 冊の本になります。あなたが 日目に記録した竹簡は 枚です。
皇帝は、1 日分の記録を探すために何冊もの本を開くことをひどく嫌います。かといって本を無駄に増やしたくもないため、完成する本の冊数を 冊以下に制限しました。皇帝の機嫌をうかがうのは容易ではないので、あなたは決められた規則に従って本を作ることにしました。
最初の行に整数 と が空白区切りで与えられます。
2 行目に整数 が空白区切りで与えられます。
条件を満たす最小の容量 を出力してください。
最初の例では、容量を にすると、最初の本に 1 日目と 2 日目の竹簡をつなぎます。2 冊目には 3 日目の竹簡を、3 冊目には 4 日目と 5 日目の竹簡をつなぎます。容量が より小さいと、1 日分の竹簡が 1 冊に収まらないか、必要な本が 冊を超えます。
2 番目の例では、容量を にすると、最初の本に 1 日目と 2 日目の竹簡を、2 冊目に 3 日目の竹簡をつなぎます。容量が より小さいと、1 冊に 2 日分の竹簡をつなぐことができないので、条件を満たしません。
竹簡は最初の日から最後の日まで、記録された順につなぎます。1 日分の竹簡を複数の本に分けることはできませんが、異なる日の竹簡を同じ本につなぐことはできます。日を区切るための空白の竹簡は入れません。
すべての本の容量を同じ正の整数 に定める必要があります。1 冊には最大 枚の竹簡をつなげられ、どの日の竹簡も 1 冊に収まらなければなりません。本が重くなりすぎないように、容量をできるだけ小さくしようと考えています。
最初の本には、まだ竹簡がありません。その日の竹簡をすべて加えたときの枚数が 以下なら、現在の本に続けてつなぎます。 を超えるなら、現在の本にはもう竹簡を加えず、次の本にその日の竹簡をすべてつなぎます。枚数がちょうど になる場合は、現在の本につなぎます。
すべての竹簡をつなぎ終えたとき、完成する本が 冊以下となる最小の容量 を求めてください。
