Weapon Purchase Optimization

You are given a shop that sells n weapons. The i^th weapon has a strength of \(p_i\) and a cost of \(c_i\).

You are also given two integers \(P\) and \(Q\). Your task is to determine whether there exists a subset of weapons such that the total strength is at least \(P\) (i.e. \(\sum p_i \ge P\)) and the total cost does not exceed \(Q\) (i.e. \(\sum c_i \le Q\)). If such a subset exists, output the minimum total cost required to achieve a total strength of at least \(P\); otherwise, output \(-1\).

Note: Each weapon can be purchased at most once.

inputFormat

The input begins with a single line containing three integers \(n\), \(P\), and \(Q\) where \(n\) is the number of weapons. This is followed by \(n\) lines, each containing two integers \(p_i\) and \(c_i\) representing the strength and cost of the \(i^th\) weapon respectively.

Constraints: The constraints are such that a solution using dynamic programming with a cost dimension up to \(Q\) is feasible.

outputFormat

Output a single integer representing the minimum total cost required to achieve a total strength of at least \(P\) while keeping the total cost within \(Q\). If no such subset exists, output \(-1\).

sample

3 10 15
5 4
6 7
7 10

11