---

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using HyperGrid = std::vector<std::vector<std::vector<std::vector<int>>>>;


struct State
{
    long long cost;
    int t, z, y, x;

    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

long long findMinEnergyPath(const HyperGrid& grid) {
    int T = grid.size();
    int Z = grid[0].size();
    int Y = grid[0][0].size();
    int X = grid[0][0][0].size();
    
    if (grid[0][0][0][0] == -1 || grid[T - 1][Z - 1][Y - 1][X - 1] == -1) {
        return -1;
    }
    const long long INF = 1e18;
    std::vector<std::vector<std::vector<std::vector<long long>>>> dist(
        T, std::vector<std::vector<std::vector<long long>>>(
            Z, std::vector<std::vector<long long>>(
                Y, std::vector<long long>(X, INF)
            )));

    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    // nach toch
    long long startCost = grid[0][0][0][0];
    dist[0][0][0][0] = startCost;
    pq.push({ startCost,0,0,0,0 });

    const int dt[8] = { 1,-1,0,0,0,0,0,0 };
    const int dz[8] = { 0,0,1-1,0,0,0,0,0 };
    const int dy[8] = { 0,0,0,0,1,-1,0,0 };
    const int dx[8] = { 0,0,0,0,0,0,1,-1 };
    while (!pq.empty()) {
        State top = pq.top();
        pq.pop();
        long long curCost = top.cost;
        int t = top.t;
        int z = top.z;
        int y = top.y;
        int x = top.x;
        if (curCost > dist[t][z][y][x]) continue;

        if (t == T - 1 && z == Z - 1 && y == Y - 1 && x == X - 1) {
            return curCost;
        }
        for (int i = 0;i < 8; i++) {
            int nt = t + dt[i];
            int nz = z + dz[i];
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (nt < 0 || nt >= T || nz < 0 || nz >= Z || ny < 0 || ny >= Y || nx < 0 || nx >= X) {
                continue;
            }
            int cellVal = grid[nt][nz][ny][nx];
            if (cellVal == -1) continue;

            long long stepCost = 0;
            int final_t = nt, final_z = nz, final_y = ny, final_x = nx;

            if (cellVal == -2) {
                int pt = T - 1 - nt;
                int pz = Z - 1 - nz;
                int py = Y - 1 - nz;
                int px = X - 1 - nx;

                if (grid[pt][pz][py][px] < 0) continue;
                final_t = pt;
                final_z = pz;
                final_y = py;
                final_x = px;
                stepCost = 0;
            } else {
                stepCost = cellVal;
            }

            if (curCost + stepCost < dist[final_t][final_z][final_y][final_x]) {
                dist[final_t][final_z][final_y][final_x] = curCost + stepCost;
                pq.push({ curCost + stepCost, final_t ,final_z,final_y,final_x });
            }

        }
    }
    return -1;
}


int main()
{
    HyperGrid grid (2, std::vector<std::vector<std::vector<int>>>
        (2, std::vector<std::vector<int>>
        (2, std::vector<int>(2, 5))));

    grid[0][0][0][0] = 10;
    grid[0][0][0][1] = -2;
    grid[1][1][1][0] = 0;
    grid[1][1][1][1] = 2;

    std::cout << "min cost path:               suka ya ato cdelal@" << findMinEnergyPath(grid) << "\n";
    return 0;
}