题目描述

小 z 和他的小伙伴们准备一起去游乐场玩，他们一共有 $n$ 个人。由于时间紧迫，他们决定在校门口拼出租车前往游乐场。

现在是 $0$ 时刻，当前的位置到游乐场需要支付给出租车师傅 $d$ 元（按车次计算，不管车里坐了多少人）。假设 坐上 T 分钟后的出租车恰能赶上入场截至时间，如果在 $T$ 分钟后经过校门口的出租车，由于已经赶不上入场时间，可以忽略不计。

在接下来的 $T$ 分钟内，会有 $K$ 辆出租车依次经过校门口。第 $i$ 辆出租车到达校门口的时间是 $t_i$ 分钟，车上的剩余座位数是 $Z_i$。小 z 和他的小伙伴们可以选择上这辆车（最多上 $Z_i$ 个人），也可以选择不上（即上 $0$ 个人）。

俗话说，​时间就是金钱​。在这里，每个小伙伴在校门口等待出租车的分钟数，就等同于花了相同多的钱（比如某个小伙伴等了 $15$ 分钟才上车，那就相当于他额外花了 $15$ 元钱）。

在保证所有小伙伴都能在 $T$ 分钟内到达游乐场的前提下，计算他们最少需要花多少钱 ？（包括车费和等待时间折算的钱）。

数据范围：对于 $100\%$ 的数据，满足 $n,K,d,T \le 100$，$1 \le Z_i \le 4$，$1 \le t_i \le t_{i+1} \le T$。

输入格式

每组数据以四个整数 $n$，$K$，$d$，$T$ 开始，具体含义参见题目描述。

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

时间按照先后顺序。

输出格式

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

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

2 2 10 5
1 1
2 2

14

5 4 20 50
20 2
35 1
40 3
50 4

200

样例数据1解释: 共两个人，全部选择第二辆出租车，车费 $10$ 元，等待时间花费为 $2*2$，共花费 $14$ 元钱。

样例数据2解释: 共 $5$ 个人，两个人选择第1辆出租车，在第1辆车上等待时间花费为 $2*20$，剩余三个人选择第3辆车， 在第3辆车上等待时间花费为 $3*40$，共需要两辆车，车费 $2*20$，共花费 $200$。