Maximum Block Length Construction

In this problem, you are given a set of component types, each with a specified size and count. Your task is to construct a block by selecting components such that the total length is as large as possible without exceeding a given limit L.

Formally, you are given an integer (K) representing the number of component types. For each type, you are given its size (s_i) and the maximum number (c_i) available of that type. You must choose non-negative integers (k_i) (with (0 \leq k_i \leq c_i)) such that the total length (T = \sum_{i=1}^{K} k_i \times s_i) is maximized, while (T \leq L).

The goal is to compute the maximum achievable (T).

inputFormat

Input is read from standard input (stdin). The first input line contains an integer (K), the number of component types. Each of the following (K) lines contains two integers representing the size and available count of that component type. The last line contains an integer (L), the maximum allowable total length.

outputFormat

Output to standard output (stdout) a single integer representing the maximum possible block length that can be constructed without exceeding (L).## sample

3
5 3
10 2
3 8
25

25