#include <stdio.h> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <functional> #include <map> #include <iomanip> #include <math.h> #include <stack> #include <queue> #include <bitset> #include <cstdlib> #include <tuple> #include <cctype> #include <ctype.h> #include <set> #include <sstream> using namespace std; int main() { int i, j; int n, V; vector<int>v, w; //vector<int>dp(100005, 0); vector<vector<int>>dp(105, vector<int>(100005, 0)); vector<vector<int>>flag(100005); cin >> n; for (i = 0; i < n; i++) { int num1, num2; cin >> num1 >> num2; v.push_back(num1); w.push_back(num2); //dp[num2] = num1; //flag[num2].push_back(i); } cin >> V; for (i = 0; i < n; i++) { dp[i][w[i]] = max(dp[i][w[i]], v[i]); for (int W = 1; W <= 100000; W++) { //for (int W = 1000; W >= 1; W--) { if (W >= w[i] && W - w[i] != w[i]) { dp[i + 1][W] = max(dp[i][W], dp[i][W - w[i]] + v[i]); } else { //dp[i][W] = dp[i][W - 1]; //dp[i + 1][W] = dp[i][W]; dp[i + 1][W] = max( dp[i][W], dp[i][W - 1]); } } } int maxn = -1, minn = 99999999; for (i = 1; i <= 100000; i++) { if (dp[n][i] == V) { maxn = max(maxn, i); minn = min(minn, i); } } cout << minn << endl; if (maxn >= 100000) { cout << "inf" << endl; } else { cout << maxn << endl; } ////dp[0] = 1; //for (int W = 1; W <= 100000; W++) { // bool flag2 = false; // for (i = 0; i < n; i++) { // if (W >= w[i]) { // if (W - w[i] != 0 && dp[W - w[i]] == 0) { // continue; // } // int num = 0; // /* if (dp[W - w[i]] == 0) { // num = 0; // } // else {*/ // auto itr = std::find(flag[W - w[i]].begin(), flag[W - w[i]].end(), i); // if (itr != flag[W - w[i]].end()) { // //dp[W] = dp[W - 1]; // //flag[W] = flag[W - 1]; // continue; // } // else { // num = dp[W - w[i]] + v[i]; // //if (W - w[i] != 0) { // //flag[W - w[i]].push_back(i); // flag[W].push_back(i); // //} // //flag[W - w[i]].push_back(i); // //flag[W] = flag[W - w[i]]; // //flag[W].push_back(i); // //flag[W].push_back(flag[W - w[i]]); // } // //} // if (num > dp[W - 1]) { // dp[W] = num; // flag2 = true; // } // else if (num < dp[W - 1]) { // //dp[W] = dp[W - 1]; // //flag[W] = flag[W - 1]; // } // //dp[W] = max({ dp[W], num, dp[W - 1] }); // } // } // if (flag2 == false) { // dp[W] = dp[W - 1]; // flag[W] = flag[W - 1]; // } //} //vector<int>list; //for (i = 0; i <= 1000; i++) { // if (dp[i] == V) { // list.push_back(i); // } //} //sort(list.begin(), list.end()); //if (list.size() >= 1 && list[0] == 0){ // list.erase(list.begin()); //} //if (list.size() == 0) { //} //else { // // int minn = list[0]; // cout << minn << endl; // //if (list[list.size() - 1] == dp[minn]) { // if (dp[999] == dp[minn]) { // cout << "inf" << endl; // } // else { // cout << list[list.size() - 1] << endl; // } //} getchar(); getchar(); return 0; }