题目

城市中有一条长度为 $n$ 的道路，每隔 $1$ 的长度有一个公交车站，车站的编号从 $0$ 到 $n$，市政府在 $0$ 号车站的位置。

城市中同时有 $n$ 趟公交线路，第 $i$ 条公交线路的起点站为 $i-1$。公交车站 $i(0\leq i\leq n)$ 有两个属性 $c_i$ 和 $v_i$，代表从这个公交车站出发的公交车的性质。

$c_i$ 代表这个从 $i$ 出发的公交车，相邻两个停靠站之间的距离。$v_i$ 表示每坐一站的花费。

注意，一辆公交车出发后会向 $n$ 号车站的方向行进。同时，一名乘客只能从起点站上车，但可以从任意停靠站下车。

形式化地：

• 如果在第 $i$ 个公交车站上车，你可以选择一个正整数 $k(i+k\times c_i\leq n)$，然后在 $i+k\times c_i$ 这个站点下车，这个过程需要花费 $k\times v_i$ 的代价。

你需要分别求出从 $0$ 号车站乘公交车到 $i$ 号车站的最小花费（每个最小花费是独立的询问）。

分析

容易发现转移：

$$f_i=\min_{c_j|i-j}\left\{f_j+\dfrac{i-j}{c_j}\cdot v_j\right\}$$

转移带乘法，考虑斜率优化。但是由于 $c_i$ 的限制，不能直接优化，考虑突破这个限制：对它分类，一类 $\{c_i,i\bmod c_i\}$ 到达的地点都一样，维护 $\text{cmax}^2$ 个类即可。然后，把转移方程看作是直线方程。斜率公式为：

$$\begin{align*}f_j+\dfrac{i\cdot v_j}{c_j}-\dfrac{j\cdot v_j}{c_j}&\leq f_k+\dfrac{i\cdot v_k}{c_k}-\dfrac{k\cdot v_k}{c_k}\f_j-f_k-\dfrac{j\cdot v_j}{c_j}+\dfrac{k\cdot v_k}{c_k}&\leq \dfrac{i\cdot v_k}{c_k}-\dfrac{i\cdot v_j}{c_j}\\dfrac{f_j-f_k-\dfrac{j\cdot v_j}{c_j}+\dfrac{k\cdot v_k}{c_k}}{v_k-v_j}&\leq \dfrac{i}{c} \tag{1}\end{align*}$$

其中 $(1)$ 式中，在同一类 $c_j=c_k$，这里直接化作 $c$。

代码

const int N = 1e6 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= 	'9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, mxc;
int c[N], v[N];
vector<int> st[11][11];
int f[N];

double slope(int i, int j) {
	if (v[i] == v[j]) return 1010580540;
	return (double)(f[i] - f[j] - i * v[i] / c[i] + j * v[j] / c[j]) / (v[j] - v[i]);
}

int calc(int i, int j) {
	return f[j] + (i - j) / c[j] * v[j];
}

int main() {
	freopen("bus.in", "r", stdin);
	freopen("bus.out", "w", stdout);
	n = Read(), mxc = Read();
	for (int i = 0; i < n; i++) c[i] = Read(), v[i] = Read();
	memset (f, 60, sizeof f);
	f[0] = 0;
	for (int i = 0; i < n; i++) {
		int x = c[i], y = i % c[i];
		while (!st[x][y].empty() && v[i] <= v[st[x][y][st[x][y].size() - 1]]) st[x][y].pop_back();
		while (st[x][y].size() >= 2 && 
			slope(i, st[x][y][st[x][y].size() - 1]) >=
			slope(st[x][y][st[x][y].size() - 2], st[x][y][st[x][y].size() - 1])) st[x][y].pop_back();
		st[x][y].push_back(i);
		for (int j = 1; j <= mxc; j++) {
			x = j, y = (i + 1) % j;
			while (st[x][y].size() >= 2 && calc(i + 1, st[x][y][st[x][y].size() - 1]) >=
				calc(i + 1, st[x][y][st[x][y].size() - 2])) st[x][y].pop_back();
			if (!st[x][y].empty()) f[i + 1] = min(f[i + 1], calc(i + 1, st[x][y][st[x][y].size() - 1]));
		}
	}
	for (int i = 1; i <= n; i++) 
		if (f[i] >= 1010580540) printf ("-1 ");
		else printf ("%d ", f[i]);
	return 0;
}