RWY停车

题目描述:

RWY有一辆赛车,有一天他开着他的赛车出去兜(lang)(bi),回来之后发现自己家门口的车位上停满了车,而且每个车位对所停车辆的长度有限制,也就是说,RWY的赛车不一定能停入每一个车位,所以他必须等到自己的车能停入某一个空车位为止。
幸好,RWY有预知未来的能力,他知道什么时候会有车开出车位,但是车辆太多了,他想请你直接告诉他,至少要等待多久才能停好自己的车,这样他就可以乘坐时光机穿越时空,直接将车停好(车辆进出的时间均不计)。

输入格式:

第一行输入两个非负整数n,q,表示有n个车位,将有q辆车开出车位。
第二行输入n个实数,第i个数表示第i个车位可以容纳汽车的最大长度。
第三行输入q个正整数对(x,y),表示第x个车位上的车将在y时刻开出车位。
最后一行输入一个实数s,表示RWY的赛车长度。

输出格式:

输出一行一个数,表示RWY需要等候的最少时间。如果RWY在这q次操作之后还不能停好自己的车,输出“Impossible Solution!”。

样例输入:

8 3
1.4 2.5 1.3 1.7 2.15 2.46 2.99 0.8
2 5 4 8 7 12
2.9

样例输出:

12

提示:

对于50%的数据,0<=q<=n<=100
对于100%的数据,0<=q<=n<=10000,保证每个实数不超过107
时间限制: 1000ms
空间限制: 128MB

来源: 2016新生欢乐赛1