Pagini recente » Cod sursa (job #1717696) | Cod sursa (job #560101) | Cod sursa (job #2524273) | Cod sursa (job #2692742) | Cod sursa (job #2502481)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int n, G;
int e[1005], g[1005];
int dp[2][5005]; //dp[i][j] = cost minim pentru a avea cel putin energia j, folosind primele i elemente
int k;
int s;
inline void MakeInf()
{
for (int i = 0; i <= G; i++)
dp[k][i] = 2e9;
}
inline void read()
{
fin >> n >> G;
for (int i = 1; i <= n; i++)
fin >> e[i] >> g[i], s += e[i];
}
inline void solve()
{
k = 1-k;
MakeInf();
for (int i = 1; i <= n; i++)
{
k = 1 - k;
MakeInf();
for (int j = 1; j <= G; j++)
{
if (j <= e[i])
dp[k][j] = min(dp[1 - k][j], g[i]);
else
dp[k][j] = min(dp[1 - k][j], dp[1 - k][j - e[i]] + g[i]);
}
}
fout << dp[k][G];
}
int main()
{
read();
if (s < G)
fout << "-1";
else
solve();
return 0;
}