パイプラインで $n$ 個のジョブを実行するスケジュールを決める必要があります。ジョブは列をなしており、ジョブ $i$ の仕事量は $a_i$ です。パイプラインは直列につながった $m$ 個のステージからなります。

処理を開始する前に、整数 $t$ ($0 \le t \le n$) を選ぶことができます。これにより、先頭の $t$ 個のジョブを相対的な順序を変えずに末尾へ移動し、$a_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t$ という列を得ます。$t = 0$ または $t = n$ を選んだ場合、列は変わりません。

次に、得られた列を高々 $k$ 個の空でない連続区間に分割し、それぞれをバッチとする必要があります。バッチの仕事量は、そのバッチに含まれるジョブの仕事量の総和です。

その後、バッチは順番にパイプラインへ入ります。各バッチはステージ $1, 2, \ldots, m$ をこの順に通過し、各ステージでその仕事量に等しい時間を要します。各ステージは、列におけるバッチの左から右への順序に従って、一度に高々 1 つのバッチを処理します。あるステージでの処理を終えた後、バッチは次のステージが利用可能になるまで待つことができます。待っている間、そのバッチは直前のステージを占有しないため、そのステージは次のバッチを処理できます。異なるステージは異なるバッチを同時に処理できます。

パイプラインは時刻 $0$ に処理を開始します。すべてのジョブができるだけ早く完了するように、末尾へ移動する接頭辞とバッチへの分割を選んでください。

入力

1 行目には 3 つの整数 $n, m, k$ ($1 \le n, m \le 5 \times 10^5$, $1 \le k \le n$) が与えられます。それぞれジョブの個数、ステージの個数、バッチの個数の上限を表します。

2 行目には $n$ 個の整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) が与えられ、各ジョブの仕事量を表します。

出力

すべてのジョブが完了する時刻として考えられる最小値を、1 つの整数として出力してください。

入出力例

入力 1

4 3 2
3 1 4 2

出力 1

20

注記

最適な選択の 1 つは、接頭辞 $[3, 1, 4]$ を末尾へ移動して列 $[2, 3, 1, 4]$ を得て、それを 2 つのバッチ $[2, 3]$ と $[1, 4]$ に分割することです。どちらのバッチも仕事量は $5$ です。それぞれ時刻 $0$ と $5$ に最初のステージで処理を開始し、時刻 $15$ と $20$ に 3 番目のステージでの処理を終えることができます。したがって、すべてのジョブは時刻 $20$ に完了し、これが可能な最小の時刻です。