问题 1122 --【基础】见缝插车

1122: 【基础】见缝插车

题目描述

  

史上最烂停车场问世了:一排从左往右编号为1..m的m个连续车位,宽度竟然大大小小。没办法,有些车位宽度过窄以至于不得不一辆车泊在连续的几个车位上。现给出每个车位是否被占用的信息ai(0或1)和车位宽度bi,试求宽度为n的汽车从最左边驶入找到的第一个泊得下的车位位置编号。

输入

第1行:两个空格隔开的整数m(1 <= m <=10000)和n(1 <= n <= 2000)
接下来的m行,表示编号为1..m的车位信息。每行两个整数:ai(0 <= ai <= 1)和bi(1 <= bi <= 1000)。ai为0表示该车位为空,1表示该车位已被其他车辆占用。

输出

一行,空格隔开的2个整数,表示找到的第一个停得下的车位的开始位置和结束位置。1个或连续的多个空车位的总宽度大于汽车宽度才算能停得进去。如果没有找到停得下的车位,则输出“-1”。

样例输入输出

输入#1 复制
6 5
0 3
1 16
0 2
0 6
0 2
1 20
输出#1 复制
3 4

提示

序号 标题 作者 发表时间 费用 订购数 操作