Description

They each have an affection value for the other. Define their intimacy level as the sum of their affection values.

If their intimacy level reaches at least $v$, they will get together. Their future happiness will depend on the absolute value of the difference between their affection values; the smaller this value is, the happier their life will be.

Currently, both of their affection values are $0$. Xiao Ming has $n$ tasks he can do. Each task can increase his affection for Xiao Hong by $a_i$ points and increase Xiao Hong's affection for him by $b_i$ points (possibly negative).

Xiao Ming may choose any subset of the tasks to do. Please help Xiao Ming find how to make their life happier (that is, under the premise that they get together, compute the minimum absolute difference between their affection values).

Input Format

The first line contains two positive integers $n, v$.

Then follow $n$ lines, each containing two space-separated integers $a_i, b_i$.

Output Format

Output one non-negative integer, the minimum absolute difference between their affection values under the premise that they get together. If they cannot get together no matter what, output -1.

4 15
5 6
-1 8
7 2
1 0

3

Hint

Constraints

• For $20\%$ of the testdata, it is guaranteed that $n \le 10$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 30$, $1 \le \lvert a_i \rvert, \lvert b_i \rvert \le 100$.

Translated by ChatGPT 5