import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args){ Main main = new Main(); main.solveC(); } private void solveA() { Scanner sc = new Scanner(System.in); String line = sc.nextLine(); int h = c2i(line.charAt(0)) * 10 + c2i(line.charAt(1)); int m = c2i(line.charAt(3)) * 10 + c2i(line.charAt(4)); m += 5; if (m >= 60) { m -= 60; h += 1; h = h % 24; } System.out.printf("%02d:%02d", h, m); } private int c2i(char c) { return c - '0'; } private void solveB() { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); long M = sc.nextLong(); long pp = 0; long p = 1; for (int n = 3; n <= N; n++) { long now = (pp + p) % M; pp = p; p = now; } System.out.println(p); } private void solveC() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); List list = new ArrayList<>(); for (int i = 0; i < N; i++) { Budget b = new Budget(); b.v = sc.nextInt(); b.w = sc.nextInt(); list.add(b); } int V = sc.nextInt(); int MAX_W = 1020001; int[] values = new int[MAX_W]; Set set = new HashSet<>(); set.add(0); for (Budget b : list) { Set next_set = new HashSet<>(); for (int weight : set) { int tmp_v = values[weight]; int next_v = tmp_v + b.v; int next_w = weight + b.w; if (next_w < MAX_W && next_v > values[next_w]) { values[next_w] = next_v; if (next_v < V) { next_set.add(next_w); } } next_set.add(weight); } set = next_set; } int min = 1; Integer max = null; for (int wi = 0; wi < MAX_W; wi++) { if (min == 1 && V > 0 && values[wi] == V) { min = wi; } if (max == null && values[wi] > V) { max = wi; } } System.out.println(min); System.out.println(max == null ? "inf" : max - 1); } class Budget { int v; int w; public int getValue() { return v; } public int getWeight() { return w; } } }