#include <iostream>
#include <vector>
#include <compare>
#include <absl/time/clock.h>
#include <absl/algorithm/container.h>
using namespace std;

//#############
//#...........#
//###B#B#C#D###
//  #D#C#B#A#
//  #D#B#A#C#
//  #D#C#A#A#
//  #########

enum Hall {
    L1, L2, TO1, TO2, TO3, R1, R2
};

struct State {
    array<array<char, 4>, 4> bins;
    // l1, l2, to1[3], to2[4], to3[5], r1[6], r2[7].
    array<char, 7> hall;
};

bool PathFree(const State &s, Hall hall, int bin) {
    switch (hall) {
        case L1:
            if (s.hall[L2] != '.') return false;
        case L2:
            if (bin >= 1 && s.hall[TO1] != '.') return false;
            if (bin >= 2 && s.hall[TO2] != '.') return false;
            if (bin >= 3 && s.hall[TO3] != '.') return false;
            return true;
        case TO1:
            if (bin >= 2 && s.hall[TO2] != '.') return false;
            if (bin >= 3 && s.hall[TO3] != '.') return false;
            return true;
        case TO2:
            if (bin == 0 && s.hall[TO1] != '.') return false;
            if (bin == 3 && s.hall[TO3] != '.') return false;
            return true;
        case TO3:
            if (bin <= 1 && s.hall[TO2] != '.') return false;
            if (bin == 0 && s.hall[TO1] != '.') return false;
            return true;
        case R2:
            if (s.hall[R1] != '.') return false;
        case R1:
            if (bin <= 2 && s.hall[TO3] != '.') return false;
            if (bin <= 1 && s.hall[TO2] != '.') return false;
            if (bin == 0 && s.hall[TO1] != '.') return false;
            return true;
    }
}

bool CanMoveFromHallToBin(const State &s, Hall hall, int bin) {
    if (absl::c_any_of(s.bins[bin], [bin](const char &c) { return c != 'A' + bin && c   != '.'; })) return false;
    if (s.hall[hall] != 'A' + bin) return false;
    return PathFree(s, hall, bin);
}

bool CanMoveFromBinToHall(const State &s, Hall hall, int bin) {
    if (s.hall[hall] != '.') return false;
    return PathFree(s, hall, bin);
}

void print(const State &s) {
    cout << "#############" << endl;
    cout << "#" << s.hall[L1] << s.hall[L2] << "." << s.hall[TO1] << "." << s.hall[TO2] << "." << s.hall[TO3] << "."
         << s.hall[R1] << s.hall[R2] << "#" << endl;
    for (int i = 3; i >= 0; --i) {
        cout << "  #";
        for (int b = 0; b < 4; ++b) {
            cout << s.bins[b][i] << "#";
        }
        cout << "  " << endl;
    }
    cout << "  #########" << endl << endl;
}

bool IsWin(const State &s) {
    char c = 'A';
    for (const auto bin: s.bins) {
        if (!absl::c_all_of(bin, [c](const char cb) { return cb == c; })) return false;
        ++c;
    }
    return true;
}

int Dist(const State &s, Hall h, int bin) {
    int d = absl::c_count(s.bins[bin], '.');
    switch (h) {
        case L1:
            ++d;
        case L2:
            if (bin == 0) return d + 1;
            if (bin == 1) return d + 3;
            if (bin == 2) return d + 5;
            if (bin == 3) return d + 7;
        case TO1:
            if (bin == 0) return d + 1;
            if (bin == 1) return d + 1;
            if (bin == 2) return d + 3;
            if (bin == 3) return d + 5;
        case TO2:
            if (bin == 0) return d + 3;
            if (bin == 1) return d + 1;
            if (bin == 2) return d + 1;
            if (bin == 3) return d + 3;
        case TO3:
            if (bin == 0) return d + 5;
            if (bin == 1) return d + 3;
            if (bin == 2) return d + 1;
            if (bin == 3) return d + 1;
        case R2:
            ++d;
        case R1:
            if (bin == 0) return d + 7;
            if (bin == 1) return d + 5;
            if (bin == 2) return d + 3;
            if (bin == 3) return d + 1;
    }
    return d;
}

const array<int, 4> V{{1, 10, 100, 1000}};


bool TryPark(State& s,  int& score) {
    for (int h = 0; h < 7; ++h) {
        char c = s.hall[h];
        if (c == '.') continue;
        for (int b = 0; b < 4; ++b) {
            if (CanMoveFromHallToBin(s, Hall(h), b)) {
                score += Dist(s, Hall(h), b) * V[c - 'A'];
                for (int i = 0; i < 4; ++i) {
                    if (s.bins[b][i] == '.') {
                        s.bins[b][i] = c;
                        s.hall[h] = '.';
                        return true;
                    }
                }
            }
        }
    }
    return false;
}


int Play(State &s, int score, vector<State> stack) {
    while (true) {
       if (!TryPark(s, score)) break;
    }
    if (IsWin(s)) {
        if (score == 47625) {
            cout << "Best solution: " << stack.size() << endl;
            for (const auto& s: stack) {
                print(s);
                cout << endl;
            }
        }
        return score;
    }

    int ans = 1e9;
    for (int b = 0; b < 4; ++b) {
        if (absl::c_all_of(s.bins[b], [b](const char c) { return (c == 'A' + b) || (c == '.'); })) continue;
        for (int h = 0; h < 7; ++h) {
            if (!CanMoveFromBinToHall(s, Hall(h), b)) continue;
            for (int i = 3; i >= 0; --i) {
                char c = s.bins[b][i];
                if (c != '.') {
                    State newState(s);
                    newState.hall[h] = c;
                    newState.bins[b][i] = '.';
                    int newScore = score;
                    newScore += (Dist(s, Hall(h), b) + 1) * V[c - 'A'];
                    auto new_stack =  stack;
                    new_stack.push_back(newState);
                    ans = min(ans, Play(newState, newScore, new_stack));
                    break;
                }
            }
        }
    }
    return ans;
}

int main() {
    auto start = absl::Now();
    State s;
    s.bins = {{{'D', 'D', 'D', 'B'},
               {'C', 'B', 'C', 'B'},
               {'A', 'A', 'B', 'C'},
               {'A', 'C', 'A', 'D'}}};
    for (auto &c: s.hall) {
        c = '.';
    }

    cout << Play(s, 0, {}) << endl;

    return 0;
}