Description

苏半夏 正在研究信息在内存中的存储。

苏半夏 共有n 条信息，依次编号为 $1,2, \dots ,n$ ,第 $i$ 条信息的大小为 $a_i$。

苏半夏 最多可以将这些信息分为连续的 $k$ 组，每组存入一个内存单元，每组需要的存储空间为这组中所有信息大小之和。

苏半夏 可以使用压缩技术将每条信息的大小同时从 $a_i$ 变为$(a_i + x)\ mod\ m$,其中 $x$ 为一个苏半夏 自己选定的整数。

苏半夏 想要知道，这 $k$ 组信息需要的存储空间最大值最小可以是多少。

Format

Input

第一行三个正整数 $n, m, k$ 表示信息条数，压缩技术的参数以及内存单元个数。

第二行n 个空格隔开的正整数 $a_1, a_2, \dots , a_n$，表示每条信息的大小。

Output

输出一行一个整数表示这个最大值的最小值。

Samples

5 5 2
0 4 2 1 3

5

Limitation

取 $x = 3$,则$a'=[3, 2, 0, 4, 1]$,分配方案为 $\{[3, 2, 0], [4, 1]\}$ ,则需要的存储空间最大值为5。

\subsection{约定和数据范围} 对于所有测试数据,$1 \leqslant k \leqslant n \leqslant 10^5,1 \leqslant m \leqslant 1000,0 \leqslant a_i < m$。

子任务1 (30 分): $n \leqslant 20,m \leqslant 50$;

子任务2 (30 分): $n \leqslant 1000$;

子任务3 (40 分): 无特殊限制。

Tips

本题数据随机,欢迎各种乱搞