#include <iostream>
#include <vector>
#include <string>
#include <limits>
using namespace std;

class LazyTypist {
    enum class KeyDist {
        q, w, e, r, t, y, u, i, o, p,
        a = 100, s, d, f, g, h, j, k, l,
        left_shift = 200, z, x, c, v, b, n, m, dummy, right_shift,
        space1 = 303, space2, space3, space4, space5
    };
    enum class KeyRaw {
        q, w, e, r, t, y, u, i, o, p,
        a, s, d, f, g, h, j, k, l,
        left_shift, z, x, c, v, b, n, m, dummy, right_shift,
        space1, space2, space3, space4, space5, N_keys
    };
    vector<KeyDist>  RawToDistMap = {
        KeyDist::q, KeyDist::w,KeyDist::e,KeyDist::r,KeyDist::t,KeyDist::y,KeyDist::u,KeyDist::i,KeyDist::o,KeyDist::p,
        KeyDist::a,KeyDist::s,KeyDist::d,KeyDist::f,KeyDist::g,KeyDist::h,KeyDist::j,KeyDist::k,KeyDist::l,
        KeyDist::left_shift,KeyDist::z,KeyDist::x,KeyDist::c,KeyDist::v,KeyDist::b,KeyDist::n,KeyDist::m,KeyDist::dummy,KeyDist::right_shift,
        KeyDist::space1,KeyDist::space2,KeyDist::space3,KeyDist::space4,KeyDist::space5

    };

    vector<KeyRaw> CharToKeyMap;

    vector<int> distance_map;
    vector<int> ResultMap;
    int NKeys;
    int Distance(KeyDist k1, KeyDist k2) {
        return abs(static_cast<int>(k1) % 100 - static_cast<int>(k2) % 100) + abs(static_cast<int>(k1) / 100 - static_cast<int>(k2) / 100);
    }
    int Distance(KeyRaw k1, KeyRaw k2) {
        return abs(static_cast<int>(RawToDistMap[static_cast<int>(k1)]) % 100 - static_cast<int>(RawToDistMap[static_cast<int>(k2)]) % 100) 
            + abs(static_cast<int>(RawToDistMap[static_cast<int>(k1)]) / 100 - static_cast<int>(RawToDistMap[static_cast<int>(k2)]) / 100);
    }

    void InitCharToKeyMap() {
        for (int i = 0;i < 65;++i) {
            CharToKeyMap.push_back(KeyRaw::dummy);
        }
        CharToKeyMap.push_back(KeyRaw::a);
        CharToKeyMap.push_back(KeyRaw::b);
        CharToKeyMap.push_back(KeyRaw::c);
        CharToKeyMap.push_back(KeyRaw::d);
        CharToKeyMap.push_back(KeyRaw::e);
        CharToKeyMap.push_back(KeyRaw::f);
        CharToKeyMap.push_back(KeyRaw::g);
        CharToKeyMap.push_back(KeyRaw::h);
        CharToKeyMap.push_back(KeyRaw::i);
        CharToKeyMap.push_back(KeyRaw::j);
        CharToKeyMap.push_back(KeyRaw::k);
        CharToKeyMap.push_back(KeyRaw::l);
        CharToKeyMap.push_back(KeyRaw::m);
        CharToKeyMap.push_back(KeyRaw::n);
        CharToKeyMap.push_back(KeyRaw::o);
        CharToKeyMap.push_back(KeyRaw::p);
        CharToKeyMap.push_back(KeyRaw::q);
        CharToKeyMap.push_back(KeyRaw::r);
        CharToKeyMap.push_back(KeyRaw::s);
        CharToKeyMap.push_back(KeyRaw::t);
        CharToKeyMap.push_back(KeyRaw::u);
        CharToKeyMap.push_back(KeyRaw::v);
        CharToKeyMap.push_back(KeyRaw::w);
        CharToKeyMap.push_back(KeyRaw::x);
        CharToKeyMap.push_back(KeyRaw::y);
        CharToKeyMap.push_back(KeyRaw::z);
        for (int i = 91;i < 97;++i) {
            CharToKeyMap.push_back(KeyRaw::dummy);
        }
        CharToKeyMap.push_back(KeyRaw::a);
        CharToKeyMap.push_back(KeyRaw::b);
        CharToKeyMap.push_back(KeyRaw::c);
        CharToKeyMap.push_back(KeyRaw::d);
        CharToKeyMap.push_back(KeyRaw::e);
        CharToKeyMap.push_back(KeyRaw::f);
        CharToKeyMap.push_back(KeyRaw::g);
        CharToKeyMap.push_back(KeyRaw::h);
        CharToKeyMap.push_back(KeyRaw::i);
        CharToKeyMap.push_back(KeyRaw::j);
        CharToKeyMap.push_back(KeyRaw::k);
        CharToKeyMap.push_back(KeyRaw::l);
        CharToKeyMap.push_back(KeyRaw::m);
        CharToKeyMap.push_back(KeyRaw::n);
        CharToKeyMap.push_back(KeyRaw::o);
        CharToKeyMap.push_back(KeyRaw::p);
        CharToKeyMap.push_back(KeyRaw::q);
        CharToKeyMap.push_back(KeyRaw::r);
        CharToKeyMap.push_back(KeyRaw::s);
        CharToKeyMap.push_back(KeyRaw::t);
        CharToKeyMap.push_back(KeyRaw::u);
        CharToKeyMap.push_back(KeyRaw::v);
        CharToKeyMap.push_back(KeyRaw::w);
        CharToKeyMap.push_back(KeyRaw::x);
        CharToKeyMap.push_back(KeyRaw::y);
        CharToKeyMap.push_back(KeyRaw::z);
    }

    int ComputeMinDistance(const string&s, int string_pos, KeyRaw k1, KeyRaw k2) {
        int ik1 = static_cast<int>(k1);
        int ik2 = static_cast<int>(k2);
        int index = NKeys*NKeys*string_pos + NKeys*ik1 + ik2;
        int result = ResultMap[index];
        if (result != -1) return result;
        if (string_pos == 0) {
            ResultMap[index] = 0;
            return 0;
        }
        char c = s[string_pos - 1];
        bool is_possible = false;
        if (c >= 'a' && c <= 'z') {
            KeyRaw newK = CharToKeyMap[c];
            is_possible = k1 == newK || k2 == newK;
        }

        if (c >= 'A' && c <= 'Z') {
            KeyRaw newK = CharToKeyMap[c];
            is_possible = ((k1 == KeyRaw::left_shift || k1 == KeyRaw::right_shift) && k2 == newK) ||
                ((k2 == KeyRaw::left_shift || k2 == KeyRaw::right_shift) && k1 == newK);
        }
        if (c == ' ') {
            is_possible = ( k1 == KeyRaw::space1 || k1 == KeyRaw::space2 || k1 == KeyRaw::space3 || k1 == KeyRaw::space4 || k1 == KeyRaw::space5 ||
                            k2 == KeyRaw::space1 || k2 == KeyRaw::space2 || k2 == KeyRaw::space3 || k2 == KeyRaw::space4 || k2 == KeyRaw::space5);
        }
        result = numeric_limits<int>::max();
        if (is_possible) {
            for (int prev_k1 = 0;prev_k1 < NKeys;++prev_k1) {
                for (int prev_k2 = 0;prev_k2 < NKeys;++prev_k2) {
                    int prev_res = ComputeMinDistance(s, string_pos - 1, KeyRaw(prev_k1), KeyRaw(prev_k2));
                    if (prev_res == numeric_limits<int>::max()) continue;
                    result = min(result, prev_res + Distance(k1, KeyRaw(prev_k1)) + Distance(k2, KeyRaw(prev_k2)));
                }
            }
        }
        ResultMap[index] = result;
        return result;
    }
    public:
    int ComputeMinDistance(const string& s) {
        NKeys = static_cast<int>(KeyRaw::N_keys);
        InitCharToKeyMap();
        ResultMap = vector<int>(NKeys * NKeys * (s.length()+1),-1);
        for (int i = 0;i < s.length() + 1;++i) {
            for (int k1 = 0; k1 < NKeys;++k1) {
                for (int k2 = 0;k2 < NKeys;++k2) {
                    ComputeMinDistance(s, i, KeyRaw(k1), KeyRaw(k2));
                }
            }
        }
        int result = numeric_limits<int>::max();;
        for (int ik1 = 0;ik1 < NKeys;++ik1) {
            for (int ik2 = 0;ik2 < NKeys;++ik2) {
                int index = NKeys*NKeys*s.length() + NKeys*ik1 + ik2;
                result = min(result, ResultMap[index]);
            }
        }
        return result;
    }
};

int main() {
	
	LazyTypist L;
	string s = "The quick brown fox";
	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
	s = "hello world";
	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
	s = "qpalzm woskxn";
	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
	s = "Hello there DailyProgrammers";
	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
	s = "QPgizm QFpRKbi Qycn";
	cout<<s << ": "<<  L.ComputeMinDistance(s)<<endl;
	// your code goes here
	return 0;
}