Language: C

#include<cstdio>
#include<algorithm>

const int Inf = (int) (2e8);

int n, m, x[1 << 15], c[1 << 15], r[1 << 15], p[1 << 15];
int li[1 << 15], ri[1 << 15], pre[1 << 15], f[1 << 7][2], ans;

struct tree_st {
	int e[1 << 16], c[1 << 16];
	void build(int l, int r, int rt) {
		e[rt] = c[rt] = Inf;
		if (l != r) {
			int m = (l + r) >> 1;
			build(l, m, rt << 1);
			build(m + 1, r, rt << 1 | 1);
		}
	}
	void pushdown(int rt) {
		if (c[rt] == Inf) {
			return;
		}
		c[rt << 1] = std::min(c[rt << 1], c[rt]);
		e[rt << 1] = e[rt];
		c[rt << 1 | 1] = std::min(c[rt << 1 | 1], c[rt]);
		e[rt << 1 | 1] = e[rt];
		c[rt] = Inf;
	}
	void modify(int sl, int sr, int v, int l, int r, int rt) {
		if (sl > r || sr < l) {
			return;
		} else {
			if (sl <= l && r <= sr) {
				c[rt] = std::min(c[rt], v);
				e[rt] = c[rt];
			} else {
				int m = (l + r) >> 1;
				pushdown(rt);
				modify(sl, sr, v, l, m, rt << 1);
				modify(sl, sr, v, m + 1, r, rt << 1 | 1);
				e[rt] = std::min(e[rt << 1], e[rt << 1 | 1]);
			}
		}
	}
	int min(int sl, int sr, int l, int r, int rt) {
		if (sl > r || sr < l) {
			return Inf;
		} else {
			if (sl <= l && r <= sr) {
				return e[rt];
			} else {
				int m = (l + r) >> 1;
				pushdown(rt);
				int ans = Inf;
				ans = std::min(ans, min(sl, sr, l, m, rt << 1));
				ans = std::min(ans, min(sl, sr, m + 1, r, rt << 1 | 1));
				return ans;
			}
		}
	}
} tree[1 << 7][2];

inline int cost(int l, int r) {
	if (l > r) {
		return 0;
	}
	return (l ? pre[r] - pre[l - 1] : pre[r]);
}

int solve() {
	for (int i = 1; i <= m; ++i) {
		for (int j = 0; j < 2; ++j) {
			tree[i][j].build(0, n - 1, 1);
		}
	}

	ans = pre[n - 1];

	for (int i = 0; i < n; ++i) {
		f[1][0] = c[i] + cost(0, i - 1);
		f[1][1] = c[i] + cost(0, li[i] - 1);
		for (int j = 2; j <= std::min(i + 1, m); ++j) {

			f[j][0] = Inf;
			if (j - 2 <= i - 1) {
				f[j][0] = c[i] - cost(i, n - 1)
						+ tree[j - 1][1].min(j - 2, i - 1, 0, n - 1, 1);
			}

			f[j][1] = Inf;
			if (std::max(j - 2, li[i]) <= i - 1) {
				f[j][1] = std::min(f[j][1],
						c[i]
								+ tree[j - 1][0].min(std::max(j - 2, li[i]),
										i - 1, 0, n - 1, 1));
			}

			if (j - 2 <= li[i] - 1) {
				f[j][1] = std::min(f[j][1],
						c[i] - cost(li[i], n - 1)
								+ tree[j - 1][1].min(j - 2, li[i] - 1, 0, n - 1,
										1));
			}
		}

		for (int j = 1; j <= std::min(i + 1, m); ++j) {
			tree[j][0].modify(0, ri[i], f[j][0], 0, n - 1, 1);
			tree[j][1].modify(0, ri[i], f[j][0] + cost(ri[i] + 1, n - 1), 0,
					n - 1, 1);
			ans = std::min(ans, f[j][0] + cost(ri[i] + 1, n - 1));

			tree[j][0].modify(0, i, f[j][1], 0, n - 1, 1);
			tree[j][1].modify(0, i, f[j][1] + cost(i + 1, n - 1), 0, n - 1, 1);
			ans = std::min(ans, f[j][1] + cost(i + 1, n - 1));
		}

	}
	return ans;
}

int main() {
	int test = 1;
	while (scanf("%d%d", &n, &m) == 2) {
		if (n == 0 && m == 0) {
			break;
		}
		x[0] = 0;
		for (int i = 1; i < n; ++i) {
			scanf("%d", &x[i]);
		}
		for (int i = 0; i < n; ++i) {
			scanf("%d", &c[i]);
		}
		for (int i = 0; i < n; ++i) {
			scanf("%d", &r[i]);
		}
		for (int i = 0; i < n; ++i) {
			li[i] = std::lower_bound(x, x + n, x[i] - r[i]) - x;
			ri[i] = std::lower_bound(x, x + n, x[i] + r[i]) - x;
			if (ri[i] == n || x[ri[i]] > x[i] + r[i]) {
				ri[i]--;
			}
		}
		for (int i = 0; i < n; ++i) {
			scanf("%d", &p[i]);
			pre[i] = (i ? pre[i - 1] + p[i] : p[i]);
		}
		printf("Case %d: %d\n", test++, solve());
	}
	return 0;
}

Compiler output:
main.c:1:9: fatal error: cstdio: No such file or directory
    1 | #include<cstdio>
      |         ^~~~~~~~
compilation terminated.