You are given $$$n$$$ pairs of positive integers $$$(a_i, b_i)$$$. You are also given two positive integer constants $$$P$$$ and $$$Q$$$. The constraints are $$$n, a_i, b_i, P, Q \le 10^6$$$. You must choose $$$n$$$ non-negative real coefficients $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ so that all of the conditions hold:

• $$$\sum a_i x_i = a_1 x_1 + a_2 x_2 + a_3 x_3 + ... + a_n x_n \ge P$$$

• $$$\sum b_i x_i = b_1 x_1 + b_2 x_2 + b_3 x_3 + ... + b_n x_n \ge Q$$$

• The expression $$$S = \sum x_i = x_1 + x_2 + x_3 + ... + x_n$$$ is minimum.

What is the minimum value of $$$S$$$?

The limits are the usual 2 seconds and 256MB. I couldn't find an online version of this problem, only a plaintext version from some local archive. I'm guessing this is some kind of greedy problem where you only need to "choose" no more than two pairs, but so far I have no luck trying to prove my strategy (nor have I confirmed its correctness).

I have thought about simplifying down to the case of $$$n=2$$$ then hoping some algebra magic will take it all the way to every integer $$$n>2$$$. Again, I'm stuck on the transitioning part.

I would love some help from Codeforces!