城市中有一条长度为 $n$ 的道路，每隔 $1$ 的长度有一个公交车站，车站的编号从 0 到 n，市政府在 0 号车站的位置。
城市中同时有 $n$ 趟公交线路，第 $i$ 条公交线路的起点站为$i-1$ 。公交车站  $i ( 0\leq i < n) $ 有两个属性 $c_i$ 和 $v_i$，代表从这个公交车站出发的公交车的性质。
 $c_i$代表这个从 $i$  出发的公交车，相邻两个停靠站之间的距离。$v_i$ 表示每坐一站的花费。


注意，一辆公交车出发后会向 $n$ 号车站的方向行进。同时，一名乘客只能从起点站上车，但可以从任意停靠站下车。
形式化地：
- 如果在第 $i$ 个公交车站上车，你可以选择一个正整数  $k(i + k\times c_i \leq n)$ ，然后在 $i$ 这个站点下车，这个过程需要花费 $k \times v_i$ 的代价。
你需要分别求出从 0 号车站乘公交车到 $i ( 0 < i \leq n) $  号车站的最小花费（每个最小花费是独立的询问）。

输入的第一行有两个整数，$n$  和 $maxc$，分别表示道路的长度和一个关于数据范围的参数。
之后的 $n$ 行，每行两个整数，分别表示 $0$ 到 $n-1$ 号车站的 $c$ 和 $v$。

输出一行 $n$ 个整数，其中第 $i$ 个整数代表从 $0$ 号车站到 $i$ 号车站的最小花费。
特别地，若不能从 $0$ 号车站到达 $i$ 号车站，则在 $i$ 号车站的位置输出 -1。

1 1
1 1

1

9 5
2 5
5 2
5 14
1 18
4 13
3 17
1 16
1 7
5 4

-1 5 -1 10 -1 15 19 20 33