大样例下载

题目背景

在本题中，我们认为：负数除以正数的余数‌不可能为负数‌，必须满足 0 ≤ 余数 < 除数 。

题目描述

有 $N$ 个金块，第 $i$ 个金块的重量是 $W_i$。奇怪的是，有些金块的重量可能为负数。

小明有一个非常奇怪的背包，要求必须恰好装入 $3$ 个金块，且装入的金块的总重量必须恰好是 $M$ 的倍数。

问：他能装入背包的金块的总重量最大是多少？如果无解，即找不到 3 个可以装入背包的金块，则输出 No Solution! 。

输入格式

第一行：两个正整数 $N, M$。

第二行：$N$个正整数 $W_i$。

输出格式

一个整数，表示答案。

样例1输入

5 4
1 2 4 5 12

样例1输出

8

样例2输入

5 4
1 -3 5 7 -9

样例2输出

No Solution!

数据范围

100% 的数据：$1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^3, |W_i| ≤ 10^8$。