[ONTAK2010]Creative Accounting

时间限制:10s      空间限制:128MB

题目描述

给定一个长度为N的数组a和M,求一个区间[l,r],使得(\sum_{i=l}^{r}{a_i}) mod M的值最大,求出这个值,注意这里的mod是数学上的mod


输入格式

第一行两个整数N,M。
第二行N个整数a_i。


输出格式

输出一行,表示答案。


样例输入

5 13
10 9 5 -5 7


样例输出

11



提示

【数据范围】
N<=200000,M,a_i<=10^18


题目来源

By Sbullet