//dp + 滚动数组优化
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 1e5 + 10;

int dp[2][4][1010], st[N], n, k;

int main()
{
    cin >> n >> k;

    for(int i = 1; i <= n; i ++) scanf("%d", &st[i]);

    memset(dp, -0x3f, sizeof dp);
    for(int i = 1; i <= 3; i++) dp[i & 1][0][0] = 0;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j <= 3; j ++)
        {
            for(int t = 0; t < k; t ++)
            {
                //选
                if(j != 0)
                {
                   dp[i & 1][j][t] = max(dp[i & 1][j][t], dp[i - 1 & 1][j - 1][((t - st[i] % k) + k) % k] + st[i]);
                }
                //不选
                dp[i & 1][j][t] = max(dp[i & 1][j][t], dp[i - 1 & 1][j][t]);

            }
        }
    }


    int ans = -1;

    for(int i = 0; i <= 3; i ++) ans = max(ans, dp[i & 1][3][0]);

    cout << ans;

    return 0;

}

#include<iostream>

using namespace std;

const int N = 1e7 + 10;

long long int mod = 1e9 + 7;

int g[4][4]={
  {1, 1, 1, 1},
  {0, 0, 1, 1},
  {0, 1, 0, 1},
  {1, 0, 0, 0},
};

long long int dp[N][4], n;

int main()
{

    cin >> n;

    dp[1][0] = 1;

    for(int i = 1; i <= n + 1; i ++)
    {
        for(int j = 0; j < 4; j ++)
        {
            for(int k = 0; k < 4; k ++)
            {
                dp[i][k] += dp[i - 1][j] * g[j][k] % mod;
            }
        }
    }

    cout << dp[n + 1][0] % mod;

    return 0;
}

//暴搜
//遇店N次，遇花M次

#include<iostream>

using namespace std;

typedef long long int ll;

ll ans, mod = 1000000007;

int n, m;

void dfs(int x, int y, int last, int sum)//x,y记录当前已经选过 店||花 的次数，last记录上次选的是店还是花                                         //记录当前几斗酒
{



    if(x + y == n + m )              //0遇店 1遇花
    {

        if(last == 1 && sum == 0)
        {
            ans ++;
            ans = (ans % mod + mod) % mod; 
        }
        return;
    }


    for(int i = 0; i <= 1; i ++)
    {
        if(i == 0)
        {
            if(x < n)
            {
                dfs(x + 1, y, 0, sum * 2);
            }
        }
        if(i == 1)
        {
            if(y < m && sum >= 1)
            {
                dfs(x, y + 1, 1, sum - 1);
            }
        }
    }
}

int main()
{

    cin >>n >> m;
    dfs(0, 0, -1, 2);

    cout << (ans % mod + mod) % mod;

    return 0;
}

//dp做法
//dp[i][j][u][v] 经过i个店 j个花 最后u店或u花时 v斗酒

#include<iostream>

using namespace std;

const int N = 110;

typedef long long int ll;

ll dp[N + 10][N + 10][3][N + 10];

ll mod = 1000000007;

int main()
{
    int n, m;
    cin >> n >> m;

    dp[0][0][0][2] = 1;

    for(int i = 0; i <= n; i ++)
    {
        for(int j = 0; j <= m; j ++)
        {
            if(i == 0 && j == 0) continue;

            for(int u = 0; u <= 1; u ++)
            {
                for(int v = 0; v <= 110; v ++)
                {
                    //当前最后一个遇见的是花
                    if(j - 1 >= 0 && u == 1 && v + 1 <= 110)
                    {
                        dp[i][j][u][v] += dp[i][j - 1][0][v + 1] + dp[i][j - 1][1][v + 1];
                        dp[i][j][u][v] %= mod;
                    }
                    //当前最后遇见的是店
                    if(i - 1 >= 0 && u == 0 && v % 2 == 0)
                    {
                        dp[i][j][u][v] += dp[i - 1][j][1][v / 2] + dp[i - 1][j][0][v / 2];
                        dp[i][j][u][v] %= mod;
                    }

                }
            }
        }
    }

    cout << (dp[n][m][1][0] % mod + mod) % mod;

    return 0;

}

//前缀和 + 二分 n^3logn 过60%数据

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 550;

int st[N][N];

int n, m, k;

int sum(int x1, int y1, int x2, int y2)
{
    return st[x2][y2]-st[x2][y1 - 1]-st[x1 - 1][y2]+st[x1 - 1][y1 - 1];
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            scanf("%d", &st[i][j]);
            st[i][j] += st[i - 1][j] + st[i][j - 1] - st[i - 1][j - 1];
        }
    }

    int ans = 0;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            for(int u = i; u <= n; u ++)
            {
                //找到第u行，尽可能靠右边的方格
                int l = j, r = m;

                while(l < r)
                {
                    int mid = l + r >> 1;
                    int t = sum(i, j, u, mid);
                    if(t < k) l = mid + 1;
                    else r = mid;
                }
                while(sum(i, j, u, r + 1) <= k && r + 1 <= m) r ++;
                while(sum(i, j, u, r) > k && r >= j) r --;

                if(sum(i, j, u, r) > k)continue;
                else ans += r - j + 1;
            }
        }
    }

    cout << ans;

    return 0;
}

//双指针 + 前缀和 100%数据
#include<iostream>
using namespace std;

typedef long long ll;
const int N = 5e2+3;
int n, m, k;
int a[N][N];


int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    ll ans = 0;
    for(int i=1; i<=m; i++){
        for(int j=i; j<=m; j++){
            for(int s = 1, t = 1; t <= n; t ++ ){
                while(s <= t && a[t][j] - a[s - 1][j] - a[t][i - 1] + a[s - 1][i - 1] > k) s ++ ;
                if(s <= t) ans += t - s + 1;
            }
        }
    }

    cout << ans << '\n';
}

//做法一：
//暴搜
//从高位到低位以此枚举合法进位数~N进位数
#include<iostream>
#include<climits>
#include<algorithm>
using namespace std;

const int N = 1010;

typedef long long int ll;

ll A[N], B[N], t_[N];

ll k, n, m;
ll mod = 1000000007;

ll ans = LLONG_MAX;

ll nums()
{
    ll c = 1, ks = 0;
    for(ll i = n; i > 0; i --)
    {

        if(i != n) c = c * t_[i + 1] % mod;
        ks += A[i] * c;
        ks %= mod;
    }

    ll kt = 0;
    c = 1;
    for(ll i = n; i > 0; i --)
    {

        if(i != n) c = c * t_[i + 1] % mod;
        kt += B[i] * c;
        kt %= mod;
    }

    return (((ks - kt) % mod + mod) % mod);
}

void dfs(ll step)
{
    if(step == n + 1)
    {

        ll k = nums();
        ans = min(ans, k);
        return ;
    }


    for(ll i = 2; i <= k; i ++)
    {
        ll u = max(A[step], B[step]);

        if(i <= u) continue;
        if(u < 2) u = 2;

        t_[step] = i;
        dfs(step + 1);
    }
    return ;
}

int main()
{
    cin >> k;

    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> A[i];

    cin >> m;

    for(int i = 1; i <= m; i ++)
    {
        if(i <= n - m)B[i] = 0;
        cin >> B[i];
    }


    dfs(1);

    cout << ans;

    return 0;
}

//做法二：
//代码写的太乱了，思路贪心，取得A || B 对应位数数字的最大值+1即可
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int ll;

const int N = 1e5 + 10;

ll nums[N], backpack[N];

ll A[N], B[N];

int k, n, m, mod = 1000000007;

int main()
{
    cin >> k;
    cin >>n;
    for(ll i = 1; i <= n; i ++) cin >> A[i];
    cin >> m;
    for(ll i = 1; i <= m; i ++) cin >> B[i];

    for(ll i = 1; i <= n; i ++)
    {
        if(i <= n - m)
        {
            nums[i] = A[i] + 1;
            if(nums[i] <= 1) nums[i] = 2;
        }
        else
        {
            nums[i] = max(A[i], B[i - n + m]) + 1;
            if(nums[i] <= 1) nums[i] = 2;
        }
    }



    ll ans = 0, res = 0;
    ll c = 1;
    for(int i = n; i > 0; i --)
    {

        if(i != n) c = c * nums[i + 1] % mod;
        ans += A[i] * c ;
        ans %= mod;
    }
    int cnt = 1;
    for(int i = n - m + 1; i <= n; i ++)
    {
        backpack[cnt ++] = nums[i];
    }

    ll k = 1;
    for(int i = m; i > 0; i --)
    {
        if(i != m)k = k * backpack[i + 1] % mod;
        res += B[i] * k ;
        res %= mod;
    }

    cout<<((ans - res)%mod + mod) % mod;


    return 0;
}

#include<iostream>
using namespace std;
typedef long long int ll;


int main()
{
    ll a, b, n;

    cin >> a >> b >> n;

    ll res = n / (a * 5 + b * 2);

    ll cnt = 0, sums = 0, t = n - res * (a * 5 + b * 2);
    while(sums < t)
    {
        cnt ++;

        if(cnt == 6 || cnt ==7) sums += b;
        else
        {
            sums += a;
        }
    }

    cout << res * 7 + cnt;
}

//dfs暴力，50%数据
#include<iostream>

using namespace std;

typedef long long int ll;

int stopx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, stopy[8] = {1, 2, 2, 1, -1, -2, -2, -1};


int st[10][110];

ll n, m, k, res;

void dfs(ll x, ll y, ll sum)
{
    if(sum == k)
    {
        res = (res + 1) % 1000000007;
        return ;
    }

    if(y > m)
    {
        y = 1;
        x ++;
        if(x > n) return;
    }

    //不放
    dfs(x, y + 1, sum);

    //放
    if(st[x][y] == 0)
    {
        for(int i = 0; i < 8; i ++)
        {
            ll dx = x + stopx[i], dy = y +stopy[i];
            if(dx < 1 || dy < 1 || dx > n || dy > m)continue;
            st[dx][dy] ++;
        }
        st[x][y] = 1;
        dfs(x, y, sum + 1);
        st[x][y] = 0;

        for(int i = 0; i < 8; i ++)
        {
            int dx = x + stopx[i], dy = y +stopy[i];
            if(dx < 1 || dy < 1 || dx > n || dy > m)continue;
            st[dx][dy] --;
        }

    }

}

int main()
{
    cin >> n >> m >> k;
    dfs(1, 1, 0);

    cout << res % 1000000007;

    return 0;
}

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10;

typedef long long int LL;

typedef pair<LL, LL>PII;

priority_queue<PII> heap[N]; //first:结束时间 second:消耗算力

LL nums[N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%lld", &nums[i]);

    LL a, c, d, v;
    while(m --)
    {
        scanf("%lld %lld %lld %lld", &a, &c, &d, &v);

        //恢复机器c算力
        int flag = 0;
        while(! heap[c].empty())
        {
            PII q = heap[c].top();
            q.x = -q.x, q.y = -q.y;
            if(q.x > a) flag = 1;
            if(flag) break;
            nums[c] += q.y;
            heap[c].pop();
        }

        if(nums[c] >= v)
        {
            nums[c] -= v;
            PII q;
            q.x = -(a + d), q.y = -v;
            heap[c].push(q);
            cout << nums[c] << endl;
        }
        else cout << -1 <<endl;
    }
}

#include<iostream>
#include<queue>

using namespace std;

priority_queue<int> heap; //定义大根堆

void pushs(int x)
{
    heap.push(x);
}

void pops()
{
    heap.pop();
}

int tops()
{
    return heap.top();
}

int main()
{
    for(int i = 1; i <= 10; i ++) //向大根堆添加随机数
    {
        int x = rand() % 103;
        pushs(x);
    }

    while(! heap.empty())
    {
        cout << tops() << " ";
        pops();
    }

    return 0;
}

#include<iostream>

using namespace std;

typedef long long int ll;

int cnt;

struct nums
{
    int a, b;
}nums[35];


bool check(ll x)
{
    for(ll i = 2; i * i <= x; i++)
    {
        if(x % i == 0) return false;
    }
    return true;
}
int main()
{
    ll n;
    cin >> n;

    for(ll i = 2; i * i <= n; i ++)
    {
        if(n % i == 0)
        {
            int step = 0;
            while(n % i == 0)
            {
                step ++;
                n /= i;
            }
            nums[cnt].a = i;
            nums[cnt ++].b = step;
        }
    }
    ll res = 1;
    for(int i = 0; i < cnt; i ++)
    {
        if(nums[i].b % 2 == 0) continue;
        res *= nums[i].a;
    }
    if(n > 1)res *= n;
    cout << res;

    return 0;
}