[BOJ/백준] 7579 앱

N,M = map(int,input().split())
INF= float('inf')
dp = [INF]*(M+1)
apps_memory = list(map(int,input().split()))
apps_value = list(map(int,input().split()))
for i in range(N):
    memory,value = apps_memory[i],apps_value[i]
    for k in range(M,-1,-1):
        if k == 0:
            if memory >=M:
                memory = M
            dp[memory] = min(dp[memory],value)
        else:
            if dp[k]:
                num_memory = k + memory
                if num_memory >=M:
                    dp[M] = min(dp[M],dp[k]+value)
                else:
                    dp[num_memory] = min(dp[num_memory],dp[k]+value)
print(dp[M])

 

 

 

N,M = map(int,input().split())
INF= float('inf')

apps_memory = list(map(int,input().split()))
apps_value = list(map(int,input().split()))
total_sum = sum(apps_value)

dp = [0]*(total_sum+1)
result = INF
for i in range(N):
    for j in range(total_sum,apps_value[i]-1,-1):
        if j - apps_value[i] >=0:
            dp[j] = max(dp[j],dp[j-apps_value[i]]+apps_memory[i])
        if dp[j] >= M:
            result = min(j,result)

print(result)