[골3] 7579 - 앱

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

#pragma region 상하좌우 / 위치

const pair<int, int> dir[]
{
	{  1,  0 },
	{ -1,  0 },
	{  0, -1 },
	{  0,  1 },
};

#define y first
#define x second

#pragma endregion

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

#define MAX 10000

int main()
{
	FAST_IO();

	int n, m;
	cin >> n >> m;

	int a[101], c[101], dp[MAX + 1];
	fill(a, a + 101, 0);
	fill(c, c + 101, 0);
	fill(dp, dp + (MAX + 1), 0);

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

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = MAX; j > 0; j--)
		{
			// j만큼의 비용으로 확보할 수 있는 최대 메모리
			if (j >= c[i])
				dp[j] = max(dp[j], dp[j - c[i]] + a[i]);
		}
	}
	int cost = 0;

	while (dp[cost] < m)
		cost++;

	cout << cost;
	return 0;
}