40 lines
863 B
Java
40 lines
863 B
Java
package chelper;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class Task extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int s = in.nextInt();
|
|
int n = in.nextInt();
|
|
int[] a = in.nextIntArray(n);
|
|
|
|
boolean[][] dp = new boolean[2][s + 1];
|
|
dp[0][0]= true;
|
|
for (int i = 1; i < n + 1; i++) {
|
|
for (int j = 0; j < s + 1; j++) {
|
|
dp[i % 2][j] = dp[(i - 1) % 2][j];
|
|
if (j - a[i - 1] >= 0 && dp[(i - 1) % 2][j - a[i - 1]]) {
|
|
dp[i % 2][j] = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = s; i >= 0; i--) {
|
|
if (dp[n % 2][i]) {
|
|
out.println(i);
|
|
return;
|
|
}
|
|
}
|
|
out.println(0);
|
|
}
|
|
}
|