DP[i][j] : i번째 앱까지 j만큼 비용을 사용할 때 확보할 수 있는 최대 메모리
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] m, c;
static int[][] dp;
static void solve() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
m = new int[N];
c = new int[N];
dp = new int[N][10001];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
m[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
c[i] = Integer.parseInt(st.nextToken());
//dp 테이블 채우기
for (int j = 0; j < 10001; j++) {
if (c[0] <= j) dp[0][j] = m[0];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < 10001; j++) {
if (c[i] <= j)
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - c[i]] + m[i]);
else
dp[i][j] = dp[i-1][j];
}
}
for (int j = 0; j < 10001; j++) {
if (dp[N-1][j] >= M) {
bw.write(j + "\n");
break;
}
}
bw.flush();
}
public static void main(String[] args) throws IOException {
solve();
}
}
/**
* 앱 (22:00)
*
* N : 앱 개수
* M : 새로 필요한 메모리
*
* - M 바이트를 확보하기 위한 앱 비활성화의 최소 비용
* - DP[i][j] : i번째까지 j만큼의 비용을 사용할 때 확보할 수 있는 최대 메모리
*
* N M
* m1 .... mn (사용 중인 바이트 수)
* c1 .... cn (비활성화할 때의 비용)
*/