class Solution {
public:
    int sum_strings(vector<string>v){
        int sum=0;
        for(int i=0; i<v.size();i++){
            for(int j=0; j<v[i].size();j++){
                sum+=v[i][j];
            }
        }
        return sum;
    }
    int get_smallest_lex(vector<vector<string>>tickets,string cur_city, vector<string>&answer){
        vector<string>cur;
        int poz=0;
        for(int i=0; i<tickets.size();i++){
            if(tickets[i][0].compare(cur_city)==0){
                if(cur.size()==0){
                    cur = tickets[i];
                }
                else if(sum_strings(cur)>sum_strings(tickets[i])){
                    cur=tickets[i];
                }
                poz =i;
            }
        }
        answer = cur;
        return poz;

    }
    void brute_force(vector<vector<string>>tickets, string current_city, vector<string>&answer, vector<string>&optimum){

        if(tickets.size()==0){
            if(optimum.size()==0){
                optimum = answer;
            }
            else if(sum_strings(answer)<sum_strings(optimum)){
                optimum = answer;
            }
            return;
        }
        vector<string>used;
        int i = get_smallest_lex(tickets, current_city,used);
        answer.push_back(used[1]);
        tickets.erase(tickets.begin()+i);
        brute_force(tickets,used[1],answer,optimum);
        tickets.insert(tickets.begin()+i, used);                                             answer.pop_back();

    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string>answer= {{"JFK"}};
        vector<string>optimum;
        brute_force(tickets,"JFK",answer,optimum);
        return optimum;
    }
};