You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目

题目背景

某合是一个穷鬼，买东西都开拼夕夕，吃饭都吃拼好饭，坐车都坐拼车。（也就是，一个人坐车去，还是一堆人一起，总共需要支付的钱是一样的）（每辆车除司机外最多坐下 4个人）。

打到的车，可能没有乘客，可能只剩下一两个座位。

题目描述

假设某天N位和某合一样的穷鬼同学一起去团建吃饭，几个穷鬼准备和某合拼车，此时为0时刻，从校门到目的地需要支付给滴滴师傅D 元（按车次算，不管里面坐了多少 穷鬼），假如S分钟后恰能赶上饭点，那么S分钟后打到的车自然可以忽略不计了。现在给出在这 S分钟当中经过校门的所有的K辆车先后到达校门口的时间T_i及里面剩余的座位 Z_i,所有穷鬼可以选择上车几个人（不能超载），当然，也可以选择不上人，那就是不坐这辆车。

俗话说，时间就是金钱，这里某合把每个穷鬼在校门等待出租车的分钟数 等同于花了相同多的钱（例如小 x 等待了 20分钟，那相当于他额外花了20元钱）。

在保证所有穷鬼都能在开饭饭点准时到达地点的情况下，聪明的你能计算出他们最少需要花多少元钱么？

输入格式

每组数据第一行以四个整数N,K,D,S开始.

接着K行，表示第i 辆出租车在第T_i分钟到达校门，其空余的座位数为Z_i

时间按照先后顺序。

输出格式

对于每组测试数据，输出占一行，如果他们所有人能在饭点前到达地点，

则输出一个整数，代表他们最少需要花的钱（单位：元），否则请输出 impossible。

输入输出样例 #1

输入 #1

2 2 10 5
1 1
2 2

输出 #1

14

说明/提示

对于 100% 的数据，满足 N,K,D,S≤100，1≤Z_i≤4，1≤T_i≤*T_(i+1)≤*S