// dist1[0] и dist2[0] всегда - это особенность моей программы
// еще были dist1[1] и dist2[1] но они оказались не нужны

// 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;
}

// теперь надо слить 0 (next) и k-1 (prev) состояния (9 вариантов)
// примерно так
if (best < dp[0][prev] + dist1[0][prev] + dist2[0][prev] - 2 - dp[0][next]) {
    best = dp[0][prev] + dist1[0][prev] + dist2[0][prev] - 2 - dp[0][next];

    // цвета смыкающихся концов
    bestStart = 0;
    bestFinish = 0;
}


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