// 0,1,2 - цвет - никакой, 1-ой компании, 2-ой компании

dp[0][0] = 0;
dp[1][0] = dp[2][0] = 1;

for (int i = 0; i < k-1; i++) {

	//next = TODO

dp[0][next] = max(
		dp[0][prev] + dist1[0][prev] + dist2[0][prev] - 2,
		dp[1][prev] + dist1[0][prev] + dist2[0][prev] - 2,
		dp[2][prev] + dist1[0][prev] + dist2[0][prev] - 2
	);

dp[1][next] = max(
		dp[0][prev] + f(dist1[0][prev], 0, 0) + f(dist2[0][prev], 0, 0) - 1,
		dp[1][prev] + f(dist1[0][prev], 0, 1) + f(dist2[0][prev], 0, 1) - 1,
		dp[2][prev] + f(dist1[0][prev], 1, 0) + f(dist2[0][prev], 1, 0) - 1
	);

dp[2][next] = max(
		dp[0][prev] + f(dist1[0][prev], 0, 0) + f(dist2[0][prev], 0, 0) - 1,
		dp[1][prev] + f(dist1[0][prev], 1, 0) + f(dist2[0][prev], 1, 0) - 1,
		dp[2][prev] + f(dist1[0][prev], 0, 1) + f(dist2[0][prev], 0, 1) - 1
	);

	prev = next;
}


// чтоб посчитать, сколько вершин можно зохавать
int f(int x, int d0, int d1) {
	return (x % 2 == 0) ? x-d0 : x-d1;
}