# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1233288 | shre99 | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 KiB |
import java.io.*;
import java.util.*;
public class main {
// For fast input output
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader()
{ try {
if (System.getProperty("ONLINE_JUDGE") == null) {
br = new BufferedReader(new FileReader("input.txt"));
PrintStream out = new PrintStream(new FileOutputStream("output.txt"));
System.setOut(out);
} else {
br = new BufferedReader(new InputStreamReader(System.in));
}
} catch (Exception e) {
br = new BufferedReader(new InputStreamReader(System.in));
}
}
String next()
{
while (st == null || !st.hasMoreElements()) {
try {st = new StringTokenizer(br.readLine());}
catch (IOException e) {
e.printStackTrace();}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
double nextDouble() {return Double.parseDouble(next()); }
String nextLine()
{
String str = "";
try {
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
// end of fast i/o code
public static void main(String[] args) {
FastReader reader = new FastReader();
int s = reader.nextInt();
int n = reader.nextInt();
long[] currMaxVal = new long[s + 1];
while (n-- > 0) {
long v = reader.nextLong();
int w = reader.nextInt();
long k = reader.nextLong();
for(int i = s; i > 0; i--) {
int it = s - w, itCtr = 1;
k--;
while (it >= 0 && k >= 0) {
currMaxVal[i] = Math.max(currMaxVal[i], currMaxVal[it] + ((long)itCtr * v));
s -= w;
itCtr++;
k--;
}
}
}
long max = 0;
for(int i = 0; i <= s; i++) max = Math.max(max, currMaxVal[i]);
System.out.println(max);
}
}