#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 6;
int w[N][N];
int sx, sy, tx, ty;
int dist[N][N][5];
bool st[N][N][5];
struct Node
{
    int x, y, s;
};

int spfa()
{
    queue<Node> q;
    q.push({sx, sy, 1});
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy][1] = 0;

    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t.x][t.y][t.s] = false;
        for(int i = 0;i < 4;i++)
        {
            int x = dx[i] + t.x, y = dy[i] + t.y;
            if(x < 0 || x >= N || y < 0 || y >= N) continue;

            int cost = t.s * w[x][y];
            int s = cost % 4 + 1;
            if(dist[x][y][s] > dist[t.x][t.y][t.s] + cost)
            {
                dist[x][y][s] = dist[t.x][t.y][t.s] + cost;
                if(!st[x][y][s])
                {
                    q.push({x, y, s});
                    st[x][y][s] = true;
                }
            }
        }
    }
    int res = 1e8;
    for(int i = 0;i < 4;i++)
        res = min(res, dist[tx][ty][i]);

    return res;
}

int main()
{
    for(int i = 0;i < N;i++)  
        for(int j = 0;j < N;j++)
            cin >> w[i][j];

    cin >> sx >> sy >> tx >> ty;

    printf("%d\n",spfa());

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int a[555][555];

int main()
{
    int n, sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            cin >> a[i][j];

    for(int i = n;i >= 2;i--)
        for(int j = 1;j <= n;j++)
            for(int k = j + 1;k <= n;k++)
            {
                a[k][j] = a[j][k] = min(a[j][k], a[j][i] + a[i][k]);
                if (j >= i && k >= i) sum += 2 * a[j][k];
            }

    cout << sum << endl;

    return 0;
}

import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;

public class Main {

    static int N = 10010;
    static int[] a = new int[N];

    public static boolean check(int x) {
        for(int i = 2;i <= x / i;i++) {
            if(x % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws Exception{

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int cnt = 0, i = 2;
        while(true) {
            if(check(i))
                a[++cnt] = i;
            i++;
            if(cnt == 10000) break;
        }
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            int x = scan.nextInt();
            System.out.println(a[x]);
        }
    }
}

class Read {
    // 快读
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
    public boolean hasNext() {
        // TODO Auto-generated method stub
        return false;
    }
    public String readLine() throws Exception{
        st.nextToken();
        return st.sval;
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010;
int a[N];

bool check(int x)
{
    for(int i = 2;i <= x / i;i++)
    {
        if(x % i == 0) return false;
    }
    return true;
}

int main()
{
    int cnt = 0;
    int i = 2;
    while(1)
    {
        if(check(i)) 
            a[++cnt] = i;
        i++;

        if(cnt == 10000) break;
    }

    int x;
    while(cin >> x)
    {
        cout << a[x] << endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

string a, b;

bool cmp(vector<int> &A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();
    for(int i = A.size() - 1;i >= 0;i--)
    {
        if(A[i] != B[i])
        {
            return A[i] > B[i];
        }
    }
    return true;
}

// 加法
vector<int> add(vector<int> &A, vector<int> &B)
{
    if(A.size() < B.size()) return add(B, A);

    vector<int> C;

    int t = 0;
    for(int i = 0;i < A.size();i++)
    {
        t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(t);

    return C;
}

// 减法
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0;i < A.size();i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

// 乘法
vector<int> mul(vector<int> &A, vector<int> &B)
{
    vector<int> C(A.size() + B.size());
    for(int i = 0;i < A.size();i++)
    {
        for(int j = 0;j < B.size();j++) 
        {
            C[i + j] += A[i] * B[j];
        }
    }
    for(int i = 0, t = 0;i < C.size();i++)
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

void print(vector<int> A)
{
    for(int i = A.size() - 1;i >= 0;i--) cout << A[i];

    cout << endl;
}


int main()
{
    cin >> a >> b;

    int na = 1, nb = 1;
    if (a[0] == '-') na = -1, a = a.substr(1);
    if (b[0] == '-') nb = -1, b = b.substr(1);

    vector<int> A, B;
    for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1;i >= 0;i--) B.push_back(b[i] - '0');

    if(na * nb > 0)
    {
        if(na < 0) cout << '-';
        print(add(A, B));

        bool has_swap = false;
        if(!cmp(A, B))
        {
            has_swap = true;
            swap(A, B);
            swap(na, nb);
        }
        auto C = sub(A, B);
        if (na > 0 && has_swap || na < 0 && !has_swap)
        {
            if (C.size() > 1 || C[0] > 0)
                cout << '-';
        }
        print(C);

        print(mul(A, B));
    }
    else
    {
        bool has_swap = false;
        if (!cmp(A, B))
        {
            has_swap = true;
            swap(A, B);
            swap(na, nb);
        }

        if (na < 0) cout << '-';
        print(sub(A, B));

        if (na > 0 && has_swap || na < 0 && !has_swap) cout << '-';
        print(add(A, B));

        if (a != "0" && b != "0") cout << '-';
        print(mul(A, B));
    }

    return 0;
}

import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;

public class Main {

    static int[] mon = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    public static int get(String data) {
        int year = Integer.parseInt(data.substring(0, 4));
        int month = Integer.parseInt(data.substring(4, 6));
        int day = Integer.parseInt(data.substring(6));

        for(int i = 1;i < year;i++) {
            if(check(i)) day += 366;
            else day += 365;
        }

        for(int i = 1;i < month;i++ ) {
            if(check(year) && i == 2) day += mon[i] + 1;
            else day += mon[i];
        }

        return day;
    }

    public static void main(String[] args) throws Exception{

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            String s1 = scan.next();
            String s2 = scan.next();
            System.out.println(Math.abs(get(s1) - get(s2)) + 1);
        }
    }

    public static boolean check(int year) {
        return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
    }
}

class Read {
    // 快读
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
    public boolean hasNext() {
        // TODO Auto-generated method stub
        return false;
    }
    public String readLine() throws Exception{
        st.nextToken();
        return st.sval;
    }
}

import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;

public class Main {


    public static void main(String[] args) throws Exception{

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));


        Read sc = new Read();
        int n = sc.nextInt();
        Set<String> set = new HashSet<>();
        Stack<String> ss = new Stack<>();
        for(int i = 0;i < n;i++) {
            String s1 = sc.readLine();
            set.add(s1);
            ss.push(s1);
        }
        while(!ss.isEmpty()) {
            String t = ss.pop();
            if(set.contains(t)) {
                pw.println(t);
                set.remove(t);
            }
        }
        pw.close();
    }
}

class Read {
    // 快读
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
    public String readLine() throws Exception{
        st.nextToken();
        return st.sval;
    }
}

import java.util.*;
import java.math.*;

public class Main {

    static int N = 1010;
    static String str;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            String s1 = sc.nextLine();
            String res = "";
            if(s1.equals("START")) {
                String s2 = sc.nextLine();

                for(int i = 0;i < s2.length();i++) {
                    if(s2.charAt(i) >= 'A' && s2.charAt(i) <= 'Z') {
                        res += (char)((s2.charAt(i) - 'A' + 21) % 26 + 'A');
                    } else {
                        res += s2.charAt(i);
                    }
                }
                String s3 = sc.nextLine();
                if(s3.equals("END")) System.out.println(res);
            } else if(s1.equals("ENDOFINPUT")) break;
        }
    }
}

import java.util.*;
import java.math.*;

public class Main {

    static int N = 1010;
    static String str;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            str = sc.nextLine();
            PII[] node = new PII[N];
            int k = 0;
            for(int i = 0;i < str.length();i++) {
                if(Character.isLetter(str.charAt(i)))
                    node[k++] = new PII(str.charAt(i));
            }

            Arrays.sort(node, 0, k);
            for(int i = 0, j = 0;i < str.length();i++) {
                if(Character.isLetter(str.charAt(i))) System.out.print(node[j++].value);
                else System.out.print(str.charAt(i));
            }
            System.out.println();
        }
    }
}

class PII implements Comparable<PII>{
    char value;
    public PII(char value) {
        this.value = value;
    }
    public int compareTo(PII o) {
        return Integer.compare(Character.toLowerCase(value), Character.toLowerCase(o.value));
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    string str;
    while(getline(cin, str)) 
    {
        string cs;
        for(auto s: str)
            if(isalpha(s))  // isalpha()  == (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z')
                cs += s;

        stable_sort(cs.begin(), cs.end(), [](char a, char b) {   
            return tolower(a) < tolower(b);
        });

        for(int i = 0, j = 0;i < str.size();i++)
        {
            if(isalpha(str[i])) cout << cs[j++];
            else cout << str[i];
        }
        cout << endl;
    }

    return 0;
}