小学数学

题目描述

小$A$开了个饮料连锁店，连锁店共有$n$家，出售的饮料种类相同。

为了促销，小$A$决定让每家连锁店开展赠送活动。具体来说，在第$i$家商店，顾客可以用$a_{i}$个饮料瓶兑换到$b_{i}$瓶饮料和$1$个纪念币（注意不足$a_{i}$个饮料瓶则不能兑换，若$a_{i}=0$则表示不需要任何瓶子就可以兑换）。

一家店可以兑换多次，兑换得到的饮料瓶还可以继续用于兑换。你买了$s$瓶饮料，想知道用这$s$瓶饮料最多可以兑换到多少个纪念币。

输入格式

输入第一行为两个整数$n$，$s$，分别表示连锁店的数量和你买的饮料瓶数。

接下来$n$行，每行两个整数$a_{i}$，$b_{i}$，描述第$i$家饮料店的赠送活动。

输出格式

输出一行一个整数，表示最多能兑换到的纪念币数量。若能兑换到无限多个纪念币，则输出$-1$。

数据范围与提示

• 对于$30\%$的数据，$n \leq 10$，$s \leq 20$；
• 对于$50\%$的数据，$n \leq 1000$，$s \leq 10^{5}$；
• 对于$100\%$的数据，$0 \leq n \leq 10^{5}$，$0 \leq s \leq 10^{19}$，$0 \leq a_{i} \leq 10^{19}$，$0 \leq b_{i} \leq 10^{19}$。

样例

3 11
4 1
5 2
8 4

3

说明

最多兑换到$3$个纪念币。兑换过程如下：

1. 在第$1$家店用$4$瓶换$1$瓶，此时剩$11-4+1=8$瓶，有$1$个纪念币；
2. 在第$1$家店用$4$瓶换$1$瓶，此时剩$8-4+1=5$瓶，有$2$个纪念币；
3. 在第$2$家店用$5$瓶换$2$瓶，此时剩$5-5+2=2$瓶，有$3$个纪念币；

剩余的饮料瓶无法在任何店兑换，因此最多兑换到$3$个纪念币。

见maths.in

见maths.out