记录编号	385262	评测结果	AAAAAAAAAA
题目名称	[HAOI 2014]走出金字塔	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-03-20 18:19:36	内存使用	0.39 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1e4 + 10;
const int INF = 1e9 + 10;

int n, m, k, s;
int x[MAXN], y[MAXN];
int begx, begy;

inline int cal(int topx, int topy, int botx, int boty) {
	int ans = 0;
	if (topx == botx) return abs(boty - topy);

	if (not ((int)abs(topy + topx) & 1)) ans += 1, topy += (topy <= boty ? 1 : -1);
	if ((int)abs(boty + botx) & 1) ans += 1, boty += (boty <= topy ? 1 : -1);
	int deltay = abs(boty - topy);
	int deltax = botx - topx;
	if (deltax >= deltay) return ans + 2 * deltay + ((deltax - deltay) / 2) * 3 + (deltax - deltay - ((deltax - deltay) / 2));
	
	return ans + deltax + deltay;
}

inline void read() {
	scanf("%d %d %d %d", &n, &m, &k, &s);
	scanf("%d %d", &begx, &begy);
	for (int i = 1; i <= m; i++) scanf("%d %d", &x[i], &y[i]);
}

inline void solve() {
	int ans = INF;
	begy -= begx;
	for (int i = 1; i <= m; i++) {
		y[i] -= x[i];
		int tmp;
		if (x[i] < begx) tmp = cal(x[i], y[i], begx, begy);
		else tmp = cal(begx, begy, x[i], y[i]);
		ans = min(ans, tmp);
		// printf("i = %d : %d\n", i, tmp);
	}
	printf("%d\n", s - k * ans - 1 < 0 ? -1 : s - k * ans - 1);
}

int main() {
#ifdef LOCAL
	freopen("test.in", "r", stdin);
#endif
	freopen("ha14c.in", "r", stdin);
	freopen("ha14c.out", "w", stdout);
	read();
	solve();
	return 0;
}