增进感情

题目背景

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

题目描述

他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。 如果他们的亲密程度达到V,则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值,这个值越小,他们的生活将越幸福。 现在,他们对对方的好感值都为0,小明有N件事可以干,每件事可以增加他对小红的好感Ai点,并且增加小红对他的好感Bi点。(可能为负数) 小明可以任选一些事做,请你帮小明求出怎样才能让他们的生活更加幸福(求出两人在一起的前提下,好感值之差的最小绝对值即可)。

输入输出格式

输入格式


第1行,两个正整数N,V。 之后N行,每行两个空格隔开的整数Ai,Bi。

输出格式


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

输入输出样例

输入样例 #1

4 15
5 6
-1 8
7 2
1 0

输出样例 #1

3

说明

对于20%数据,N<=10。 对于全部数据,N<=30,|Ai|,|Bi|<=100. 数据比较弱