#P2080. 增进感情

增进感情

题目背景

小明和小红的感情,是慢慢发展起来的。

题目描述

他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。

如果他们的亲密程度达到 vv,则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值,这个值越小,他们的生活将越幸福。

现在,他们对对方的好感值都为 00,小明有 nn 件事可以干,每件事可以增加他对小红的好感 aia_i 点,并且增加小红对他的好感 bib_i 点。(可能为负数)

小明可以任选一些事做,请你帮小明求出怎样才能让他们的生活更加幸福(求出两人在一起的前提下,好感值之差的最小绝对值即可)。

输入格式

第一行,两个正整数 n,vn,v

之后 nn 行,每行两个空格隔开的整数 ai,bia_i,b_i

输出格式

一行,一个非负整数,表示两人在一起的前提下,好感值之差的最小绝对值。如果无论如何两人也无法在一起,输出 -1

4 15
5 6
-1 8
7 2
1 0
3

提示

数据范围与约定

  • 对于 20%20\% 数据,保证 n10n \le 10
  • 对于 100%100\% 数据,保证 1n301 \le n \le 30,$1 \le \left\vert a_i\right\vert,\left\vert b_i\right\vert \le 100$。