import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

/**
 * https://kenkoooo.com/atcoder/#/contest/show/79ed76d9-ba5f-44c8-901c-8a7d357a0e7c
 */
public class Main {

    public Main() throws IOException {
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    //    private final InputStream in = Files.newInputStream(Paths.get("C:\\Users\\ryo.suzuki\\Downloads\\02.txt"));
    private final InputStream in = System.in;
    private final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private void solve() throws IOException {
        try {
//            solveA();
//            solveB();
//            solveC();
//            solveD();
//            solveE();
            solveF();
        } finally {
            if (in != null) {
                in.close();
            }
            if (out != null) {
                out.flush();
                out.close();
            }
        }

    }

    // mods
    long MOD = (long) Math.pow(10, 9) + 7;

    /**
     * https://atcoder.jp/contests/abc068/tasks/abc068_b
     * B - Break Number
     */
    private void solveA() {
        int n = nextInt();
        {
            int res = 1;
            while (res * 2 <= n)
                res *= 2;
            out.println(res);
        }
        {
//            int res = 0;
//            int maxCnt = -1;
//            for (int i = 1; i <= n; i++) {
//                int cnt = 0;
//                int tmp = i;
//                while (tmp % 2 == 0) {
//                    tmp /= 2;
//                    cnt++;
//                }
//                if (maxCnt < cnt) {
//                    maxCnt = cnt;
//                    res = i;
//                }
//            }
//            out.println(res);
        }

    }

    /**
     * https://atcoder.jp/contests/abc115/tasks/abc115_c
     * C - Christmas Eve
     */
    private void solveB() {
        int n = nextInt();
        int k = nextInt();
        int[] h = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();
        long res = Integer.MAX_VALUE;
        for (int i = 0; i < n - k + 1; i++) {
            res = Math.min(res, h[i + k - 1] - h[i]);
        }
        out.println(res);
    }

    /**
     * https://atcoder.jp/contests/code-festival-2015-qualb/tasks/codefestival_2015_qualB_c
     * C - 旅館
     */
    private void solveC() {
        int n = nextInt();
        int m = nextInt();
        int[] a = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();
        int[] b = IntStream.range(0, m).map(i -> nextInt()).sorted().toArray();
        int idx = -1;
        for (int item : b) {
            idx = lowerBound(a, item, idx);
            if (idx >= n) {
                out.println("NO");
                return;
            }
        }
        out.println("YES");
    }

    private int lowerBound(int[] a, int val, int idx) {
        int left = idx;
        int right = a.length;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (a[mid] >= val)
                right = mid;
            else
                left = mid;
        }
        return right;
    }


    /**
     * https://atcoder.jp/contests/agc017/tasks/agc017_a
     * A - Biscuits
     * <p>
     * https://drken1215.hatenablog.com/entry/2020/04/09/150100
     * https://www.hamayanhamayan.com/entry/2017/07/10/015836
     */
    private void solveD() {
        int n = nextInt();
        int p = nextInt();
        int[] a = IntStream.range(0, n).map(i -> nextInt()).toArray();
        {
            int eve = 0;
            int odd = 0;
            for (int item : a) {
                if (item % 2 == 0)
                    eve++;
                else
                    odd++;
            }
            long resOdd = 0;
            int c = p == 1 ? 1 : 0;
            while (c <= odd) {
                resOdd += aCb(odd, c);
                c += 2;
            }
            long resEve = 1;
            for (int i = 0; i < eve; i++) {
                resEve *= 2L;
            }
            out.println(resOdd * resEve);
        }
        {
            /**
             * DP[i][p]はi番目まで使った時に何通り
             * pは余り
             */
//            long[][] dp = new long[55][2];
//            dp[0][0] = 1;
//            for (int i = 0; i < n; i++) {
//                long item = a[i];
//
//                /** i番目が偶数
//                 * 今までの偶数に今回の使う使わないで×2
//                 * 今までの奇数に今回の使う使わないで×2
//                 * i番目が奇数
//                 * 奇数だった通り数がi番目を使うことで偶数にできるので、
//                 * 今までの偶数+今までの奇数=新しい偶数
//                 * 今までの奇数に今回の使う使わないで×2
//                 */
//                if (item % 2 == 0) {
//                    dp[i + 1][0] = dp[i][0] * 2L;
//                    dp[i + 1][1] = dp[i][1] * 2L;
//                } else {
//                    dp[i + 1][0] = dp[i][0] + dp[i][1];
//                    dp[i + 1][1] = dp[i][0] + dp[i][1];
//                }
//            }
//            out.println(dp[n][p]);
        }

        {
//            long eve = 0;
//            long odd = 0;
//            for (int item : a) {
//                if (item % 2 == 0)
//                    eve++;
//                else
//                    odd++;
//            }
//            if (eve > 0 && odd == 0) {
//                if (p == 0)
//                    out.println(pow(2, eve));
//                else if (p == 1)
//                    out.println(0);
//            } else if (eve == 0 && odd > 0) {
//                if (p == 0)
//                    out.println(pow(2, odd - 1));
//                else if (p == 1)
//                    out.println(pow(2, odd - 1));
//            } else if (eve > 0 && odd > 0) {
//                if (p == 0)
//                    out.println(pow(2, n - 1));
//                else if (p == 1)
//                    out.println(pow(2, n - 1));
//            } else {
//                out.println(0);
//            }
        }
    }

    private boolean isInit = false;
    long[][] memo = new long[1010][1010];

    private long aCb(int a, int b) {
        if (!isInit) {
            for (long[] item : memo) {
                Arrays.fill(item, -1);
            }
            isInit = !isInit;
        }
        if (b == 0 || a == b)
            return 1;
        if (0 <= memo[a][b])
            return memo[a][b];
        return memo[a][b] = aCb(a - 1, b - 1) + aCb(a - 1, b);
    }

    /**
     * https://atcoder.jp/contests/abc087/tasks/arc090_b
     * D - People on a Line
     */
    private void solveE() {
        int n = nextInt();
        int m = nextInt();
        int[][] lrd = IntStream.range(0, m).mapToObj(i -> new int[]{nextInt(), nextInt(), nextInt()}).toArray(int[][]::new);
        Map<Long, GraphNode> graph = new HashMap<Long, GraphNode>();
        Arrays.stream(lrd).forEach(l -> {
            long a = l[0] - 1;
            long b = l[1] - 1;
            long d = l[2];
            graph.put(a, graph.getOrDefault(a, new GraphNode(a)));
            if (graph.get(a).getChild(b).v != CONST_INF) {
                out.println("No");
                return;
            }
            graph.get(a).addChild(b, d);
            graph.put(b, graph.getOrDefault(b, new GraphNode(b)));
            graph.get(b).addChild(a, -d);
        });
        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
//        Arrays.fill(dist, -1);
        for (int i = 1; i <= n; i++) {
            long wkI = i - 1;
            if (visited[i - 1])
                continue;
            Queue<Long> queue = new ArrayDeque<Long>();
            queue.add(wkI);
            while (!queue.isEmpty()) {
                int cnt = queue.size();
                for (int j = 0; j < cnt; j++) {
                    long from = queue.poll();
                    Map<Long, SimplePair> entry = graph.getOrDefault(from, new GraphNode(-1)).childs;
                    for (SimplePair item : entry.values()) {
                        if (visited[(int) item.k]) {
                            if (dist[(int) from] + item.v == dist[(int) item.k])
                                continue;
                            out.println("No");
                            return;
                        }
                        visited[(int) item.k] = true;
                        dist[(int) item.k] = (int) (dist[(int) from] + item.v);
                        queue.add(item.k);
                    }
                }
//                        if (dist[(int) item.k] != -1) {
//                            if (dist[(int) item.k] == dist[(int) from] + item.v)
//                                continue;
//                            out.println("No");
//                            return;
//                        }
//                        dist[(int) item.k] = dist[(int) from] + item.v;
//                        queue.add(item.k);
            }
        }
        out.println("Yes");
    }

    /**
     * https://atcoder.jp/contests/abc147/tasks/abc147_e
     * E - Balanced Path
     */
    private void solveFAC() {
        int h = nextInt();
        int w = nextInt();
        int[][] a = new int[h][w];
        int[][] b = new int[h][w];
        for (int i = 0; i < 2; i++) {
            int[][] wk = i == 0 ? a : b;
            for (int j = 0; j < h; j++) {
                for (int k = 0; k < w; k++) {
                    wk[j][k] = nextInt();
                }
            }
        }
        final int CONST_K = 80 * (h + w - 1);//80 * 80 + 100;
        {
            int[][][] dp = new int[h][w][CONST_K + 1];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    int diff = Math.abs(a[i][j] - b[i][j]);
                    if (i == 0 && j == 0) {
                        dp[i][j][diff] = 1;
                        continue;
                    }
                    for (int k = 0; k <= CONST_K; k++) {
                        if (j != 0 && dp[i][j - 1][k] == 1) {
                            dp[i][j][Math.abs(k + diff)] = 1;
                            dp[i][j][Math.abs(k - diff)] = 1;
                        }
                        if (i != 0 && dp[i - 1][j][k] == 1) {
                            dp[i][j][Math.abs(k + diff)] = 1;
                            dp[i][j][Math.abs(k - diff)] = 1;
                        }
                    }
                }
            }
            for (int i = 0; i <= CONST_K; i++) {
                if (dp[h - 1][w - 1][i] != 1)
                    continue;
                out.println(i);
                return;
            }
        }
    }

    private void solveFOut() {
        int h = nextInt();
        int w = nextInt();
        int[][] a = new int[h][w];
        int[][] b = new int[h][w];
        for (int i = 0; i < 2; i++) {
            int[][] wk = i == 0 ? a : b;
            for (int j = 0; j < h; j++) {
                for (int k = 0; k < w; k++) {
                    wk[j][k] = nextInt();
                }
            }
        }
        long[][] dp = new long[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                long diff = Math.abs(a[i][j] - b[i][j]);
                if (i == 0 && j == 0) {
                    dp[i][j] |= (1L << diff);
                    continue;
                }
                if (j != 0) {
                    dp[i][j] |= (dp[i][j - 1] << diff);
                    dp[i][j] |= (dp[i][j - 1] >> diff);
                }
                if (i != 0) {
                    dp[i][j] |= (dp[i - 1][j] << diff);
                    dp[i][j] |= (dp[i - 1][j] >> diff);
                }
            }
        }
        long res = dp[h - 1][w - 1];
        if (res < 0) {
            res = ~res;
//            res++;
            res <<= 1;
        }

        for (long i = 0; i <= 80; i++) {
            if (((res >> i) & 1L) == 1L) {
                out.println(i);
                return;
            }
        }
    }

    private void solveF() {
        int h = nextInt();
        int w = nextInt();
        int[][] a = new int[h][w];
        int[][] b = new int[h][w];
        for (int i = 0; i < 2; i++) {
            int[][] wk = i == 0 ? a : b;
            for (int j = 0; j < h; j++) {
                for (int k = 0; k < w; k++) {
                    wk[j][k] = nextInt();
                }
            }
        }
        final int CONST_K = 80 * (h + w);
        boolean[][][] dp = new boolean[h][w][CONST_K + 1];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int diff = Math.abs(a[i][j] - b[i][j]);
                if (i == 0 && j == 0) {
                    dp[i][j][diff] = true;
                    continue;
                }
                if (i != 0) {
                    for (int k = 0; k <= CONST_K; k++) {
                        if (!dp[i - 1][j][k])
                            continue;
                        dp[i][j][Math.abs(k + diff)] = true;
                        dp[i][j][Math.abs(k - diff)] = true;
                    }
                }
                if (j != 0) {
                    for (int k = 0; k <= CONST_K; k++) {
                        if (!dp[i][j - 1][k])
                            continue;
                        dp[i][j][Math.abs(k + diff)] = true;
                        dp[i][j][Math.abs(k - diff)] = true;
                    }
                }
            }
        }
        for (int i = 0; i <= CONST_K; i++) {
            if (!dp[h - 1][w - 1][i])
                continue;
            out.println(i);
            return;
        }
    }

    private void solveFTLE() {
        int h = nextInt();
        int w = nextInt();
        int[][] a = new int[h][w];
        int[][] b = new int[h][w];
        for (int i = 0; i < 2; i++) {
            int[][] wk = i == 0 ? a : b;
            for (int j = 0; j < h; j++) {
                for (int k = 0; k < w; k++) {
                    wk[j][k] = nextInt();
                }
            }
        }
        final int CONST_K = 80 * 80 * 80;
        final int CONST_INF = Integer.MIN_VALUE / 10;
        Map<Integer, Map<Integer, Set<Integer>>> dp = new HashMap<Integer, Map<Integer, Set<Integer>>>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!dp.containsKey(i))
                    dp.put(i, new HashMap<Integer, Set<Integer>>());
                if (!dp.get(i).containsKey(j))
                    dp.get(i).put(j, new HashSet<Integer>());
                int diff = Math.abs(a[i][j] - b[i][j]);
                if (i == 0 && j == 0) {
                    dp.get(i).get(j).add(diff);
                    continue;
                }
//                for (int k = 0; k <= CONST_K; k++) {
//                    if (j != 0 && dp.get(i).get(j - 1).contains(k)) {
//                        dp.get(i).get(j).add(Math.abs(k + diff));
//                        dp.get(i).get(j).add(Math.abs(k - diff));
//                    }
//                    if (i != 0 && dp.get(i - 1).get(j).contains(k)) {
//                        dp.get(i).get(j).add(Math.abs(k + diff));
//                        dp.get(i).get(j).add(Math.abs(k - diff));
//                    }
//                }
                if (j != 0) {
                    for (int k : dp.get(i).get(j - 1)) {
                        dp.get(i).get(j).add(Math.abs(k + diff));
                        dp.get(i).get(j).add(Math.abs(k - diff));
                    }
                }
                if (i != 0) {
                    for (int k : dp.get(i - 1).get(j)) {
                        dp.get(i).get(j).add(Math.abs(k + diff));
                        dp.get(i).get(j).add(Math.abs(k - diff));
                    }
                }
            }
        }
        Optional<Integer> min = dp.get(h - 1).get(w - 1).stream().min(Integer::compareTo);
        out.println(min.get().intValue());
        {
//        int[][][] dp = new int[h][w][CONST_K + 1];
//        for (int i = 0; i < h; i++) {
//            for (int j = 0; j < w; j++) {
//                Arrays.fill(dp[i][j], CONST_INF);
//            }
//        }
//        for (int i = 0; i < h; i++) {
//            for (int j = 0; j < w; j++) {
//                int diff = Math.abs(a[i][j] - b[i][j]);
//                if (i == 0 && j == 0) {
//                    dp[i][j][diff] = 1;
//                    continue;
//                }
//                if (i == 0) {
//                    for (int k = 0; k <= CONST_K; k++) {
//                        if (dp[i][j - 1][k] != 1)
//                            continue;
//                        dp[i][j][Math.abs(k + diff)] = 1;
//                        dp[i][j][Math.abs(k - diff)] = 1;
//                    }
//                } else if (j == 0) {
//                    for (int k = 0; k <= CONST_K; k++) {
//                        if (dp[i - 1][j][k] != 1)
//                            continue;
//                        dp[i][j][Math.abs(k + diff)] = 1;
//                        dp[i][j][Math.abs(k - diff)] = 1;
//                    }
//                } else {
//                    for (int k = 0; k <= CONST_K; k++) {
//                        if (dp[i][j - 1][k] == 1) {
//                            dp[i][j][Math.abs(k + diff)] = 1;
//                            dp[i][j][Math.abs(k - diff)] = 1;
//                        }
//                        if (dp[i - 1][j][k] == 1) {
//                            dp[i][j][Math.abs(k + diff)] = 1;
//                            dp[i][j][Math.abs(k - diff)] = 1;
//                        }
//                    }
//                }
//            }
//        }
//        for (int i = 0; i <= CONST_K; i++) {
//            if (dp[h - 1][w - 1][i] == CONST_INF)
//                continue;
//            out.println(i);
//            return;
//        }
        }
    }

    static final long CONST_INF = Long.MAX_VALUE / 4;


    private static class VectorCalculation {
        /**
         * 点Pと線(AB)の距離
         *
         * @param p
         * @param a
         * @param b
         * @return
         */
        private double distanceDotAndLine(DoublePair p, DoublePair a, DoublePair b) {
            DoublePair ab = new DoublePair(b.x - a.x, b.y - a.y);
            DoublePair ap = new DoublePair(p.x - a.x, p.y - a.y);

            // ベクトルAB、APの外積の絶対値が平行四辺形Dの面積になる
            double d = Math.abs(crossVector(ab, ap));

            double l = distanceVertex(a, b); // AB間の距離

            double h = d / l;
            return h;
        }

        /**
         * 2点間距離
         *
         * @param p1
         * @param p2
         * @return
         */
        private double distanceVertex(DoublePair p1, DoublePair p2) {
            double dx = p1.x - p2.x;
            double dy = p1.y - p2.y;
            return Math.sqrt(dx * dx + dy * dy);
        }

        /**
         * ベクトル外積
         *
         * @param vl
         * @param vr
         * @return
         */
        private double crossVector(DoublePair vl, DoublePair vr) {
            return vl.x * vr.y - vl.y * vr.x;
        }
    }

    private static class DoublePair implements Comparable<DoublePair> {
        double x;
        double y;

        public DoublePair(double k, double v) {
            this.x = k;
            this.y = v;
        }

        public int compareTo(DoublePair pair) {
            return Double.compare(this.y, pair.y);
        }
    }

    private static class SimplePair implements Comparable<SimplePair> {
        long k;
        long v;

        public SimplePair(int k, int v) {
            this.k = k;
            this.v = v;
        }

        public SimplePair(long k, long v) {
            this.k = k;
            this.v = v;
        }

        public int compareTo(SimplePair pair) {
            return Long.compare(this.v, pair.v);
        }
    }


    private static class SimpleGraphNode {
        private int n;
        private Map<Integer, Integer> childs;

        public SimpleGraphNode(int n) {
            this.n = n;
            childs = new HashMap<Integer, Integer>();
        }

        public void addChild(int child, int d) {
            this.childs.put(child, d);
        }
    }

    private static class SimpleGraph {

        private Map<Integer, SimpleGraphNode> graph;

        public SimpleGraph(int[][] list) {
            graph = new HashMap<Integer, SimpleGraphNode>();
            Arrays.stream(list).forEach(l -> {
                int a = l[0];
                int b = l[1];
                int d = l[2];
                graph.put(a, graph.getOrDefault(a, new SimpleGraphNode(a)));
                graph.get(a).addChild(b, d);
                graph.put(b, graph.getOrDefault(b, new SimpleGraphNode(b)));
                graph.get(b).addChild(a, d);
            });
        }

        public SimpleGraphNode getNode(int i) {
            return graph.getOrDefault(i, new SimpleGraphNode(-1));
        }

    }

    private static class GraphNode {
        private long n;
        private Map<Long, SimplePair> childs;

        public GraphNode(long n) {
            this.n = n;
            childs = new HashMap<Long, SimplePair>();
        }

        /**
         * not update
         *
         * @param child
         * @param d
         */
        public void addChild(long child, long d) {
            this.childs.put(child, this.childs.getOrDefault(child, new SimplePair(child, d)));
        }

        public SimplePair getChild(long child) {
            return this.childs.getOrDefault(child, new SimplePair(child, CONST_INF));
        }
    }

    private static class Graph {

        private Map<Long, GraphNode> graph;
        int n;

        /**
         * @param n    頂点数
         * @param list
         */
        public Graph(int n, int[][] list) {
            this.n = n;
            graph = new HashMap<Long, GraphNode>();
            /*
            隣接行列作成
            0-indexed
             */
            Arrays.stream(list).forEach(l -> {
                long a = l[0] - 1;
                long b = l[1] - 1;
                long d = l[2];
                graph.put(a, graph.getOrDefault(a, new GraphNode(a)));
                graph.get(a).addChild(b, d);
                graph.put(b, graph.getOrDefault(b, new GraphNode(b)));
                graph.get(b).addChild(a, d);
            });
            /*
            たどり着けない場所はCONST_INFで埋める
            自分へはCOST=0でたどり着ける
             */
            for (long i = 0; i < n; i++) {
                graph.put(i, graph.getOrDefault(i, new GraphNode(i)));
                GraphNode node = graph.get(i);
                for (int j = 0; j < n; j++) {
                    if (i == j)
                        node.addChild(j, 0L);
                    else
                        node.addChild(j, CONST_INF);
                }
            }
        }

        /**
         * ワーシャルフロイド
         */
        public void warshallFloyd() {
            for (long k = 0; k < n; k++) {
                for (long i = 0; i < n; i++) {
                    for (long j = 0; j < n; j++) {
                        long min = Math.min(graph.get(i).getChild(j).v, graph.get(i).getChild(k).v + graph.get(k).getChild(j).v);
                        graph.get(i).getChild(j).v = min;
                    }
                }
            }
        }

        public void partialUpdateAndWarshallFloyd(long x, long y, long w) {
            if (graph.get(x).getChild(y).v > w)
                graph.get(x).getChild(y).v = graph.get(y).getChild(x).v = w;
            long[] l = {x, y};
            for (long k : l) {
                for (long i = 0; i < n; i++) {
                    for (long j = 0; j < n; j++) {
                        if (graph.get(i).getChild(j).v > graph.get(i).getChild(k).v + graph.get(k).getChild(j).v) {
                            graph.get(i).getChild(j).v = graph.get(i).getChild(k).v + graph.get(k).getChild(j).v;
                        }
                    }
                }
            }
        }

        /**
         * 2点間の距離
         *
         * @param from
         * @param to
         * @return
         */
        public long getDistance(long from, long to) {
            return graph.get(from).getChild(to).v;
        }

    }

    public long calcSimpleCombination(long n, long m, long CONST_MOD) {
        long mole = 1;
        for (long i = 1; i <= n + m; i++) {
            mole *= i;
            mole %= CONST_MOD;
        }
        long deno = 1;
        for (long i = 1; i <= n; i++) {
            deno *= i;
            deno %= CONST_MOD;
        }
        for (int i = 1; i <= m; i++) {
            deno *= i;
            deno %= CONST_MOD;
        }
        deno = modInverse(deno, CONST_MOD);
        return (mole * deno) % CONST_MOD;
    }

    long abs(double x) {
        return (long) Math.abs(x);
    }

    long round(double x) {
        return Math.round(x);
    }

    long floor(double x) {
        return (long) Math.floor(x);
    }

    long ceil(double x) {
        return (long) Math.ceil(x);
    }

    double sqrt(double x) {
        return Math.sqrt(x);
    }

    double pow(double x, double y) {
        return Math.pow(x, y);
    }

    long pow(long x, long y) {
        return (long) Math.pow(x, y);
    }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    public long lcmMod(long... ab) {

        Map<Long, Long> ps = new HashMap<Long, Long>();

        for (int abl = 0; abl < ab.length; abl++) {
            long target = ab[abl];
            long l = target;
            for (long p = 2; p * p <= l; p++) {
                long cnt = 0;
                while (target > 1 && target % p == 0) {
                    cnt++;
                    target /= p;
                }
                if (cnt == 0)
                    continue;
                ps.put(p, Long.max(cnt, ps.getOrDefault(p, 0L)));
            }
            if (target > 1)
                ps.put(target, Long.max(1, ps.getOrDefault(target, 0L)));
        }
        long res = 1L;
        for (Map.Entry<Long, Long> e : ps.entrySet()) {
            res *= powMod(e.getKey(), e.getValue());
            res %= MOD;
        }
        return res;
    }

    int upperToInt(char a) {
        return a - 'A';
    }

    int lowerToInt(char a) {
        return a - 'a';
    }

    int numToInt(char a) {
        return a - '0';
    }

    int charToInt(char a) {
        return a >= 'a' ? lowerToInt(a) : a >= 'A' ? upperToInt(a) : numToInt(a);
    }

    char intToUpper(int a) {
        return (char) (a + 'A');
    }

    char intToLower(int a) {
        return (char) (a + 'a');
    }

    char intToNum(int a) {
        return (char) (a + '0');
    }

    void reverse(String array[]) {
        String reversed[] = new String[array.length];
        for (int i = 0; i < array.length; i++) {
            reversed[array.length - i - 1] = array[i];
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = reversed[i];
        }
    }

    void reverse(int array[]) {
        int reversed[] = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            reversed[array.length - i - 1] = array[i];
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = reversed[i];
        }
    }

    void reverse(long array[]) {
        long reversed[] = new long[array.length];
        for (int i = 0; i < array.length; i++) {
            reversed[array.length - i - 1] = array[i];
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = reversed[i];
        }
    }

    void reverse(double array[]) {
        double reversed[] = new double[array.length];
        for (int i = 0; i < array.length; i++) {
            reversed[array.length - i - 1] = array[i];
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = reversed[i];
        }
    }

    void reverse(boolean array[]) {
        boolean reversed[] = new boolean[array.length];
        for (int i = 0; i < array.length; i++) {
            reversed[array.length - i - 1] = array[i];
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = reversed[i];
        }
    }

    void fill(int array[][], int x) {
        for (int a[] : array) {
            Arrays.fill(a, x);
        }
    }

    void fill(long array[][], long x) {
        for (long a[] : array) {
            Arrays.fill(a, x);
        }
    }

    void fill(double array[][], double x) {
        for (double a[] : array) {
            Arrays.fill(a, x);
        }
    }

    void fill(boolean array[][], boolean x) {
        for (boolean a[] : array) {
            Arrays.fill(a, x);
        }
    }

    void fill(int array[][][], int x) {
        for (int a[][] : array) {
            fill(a, x);
        }
    }

    void fill(long array[][][], long x) {
        for (long a[][] : array) {
            fill(a, x);
        }
    }

    void fill(double array[][][], double x) {
        for (double a[][] : array) {
            fill(a, x);
        }
    }

    void fill(boolean array[][][], boolean x) {
        for (boolean a[][] : array) {
            fill(a, x);
        }
    }

    long L_INF = (long) 1e18 + 7;

    boolean isINF(long a) {
        return abs(a) > L_INF / 1000;
    }

    boolean isPlusINF(long a) {
        return a > 0 && isINF(a);
    }

    boolean isMinusINF(long a) {
        return isPlusINF(-a);
    }

    int I_INF = (int) 1e9 + 7;

    boolean isINF(int a) {
        return abs(a) > I_INF / 1000;
    }

    boolean isPlusINF(int a) {
        return a > 0 && isINF(a);
    }

    boolean isMinusINF(int a) {
        return isPlusINF(-a);
    }

    /**
     * 指定したx以下の素数をリストアップする
     */
    public long[] getPrimesUnderX(long x) {
        return LongStream.rangeClosed(2, x)
                .filter(i -> LongStream.rangeClosed(2, (long) Math.sqrt(i)).allMatch(j -> i % j != 0)).toArray();
    }


    public long mod(long i) {
        return i % MOD + ((i % MOD) < 0 ? MOD : 0);
    }

    long powMod(long x, long y) {
        if (y == 0) {
            return 1;
        } else {
            long tmp = powMod(x, y / 2);
            return mod(mod(tmp * tmp) * (y % 2 == 0 ? 1 : x));
        }
    }

    long inv(long x) {
        return powMod(x, MOD - 2);
    }

    int MAX_FACT = 5_000_100;
    long fact[];
    long invFact[];

    /**
     * Combination簡易版
     * 5 C 2
     * 異なる n個のものから r個を選ぶ組み合わせの総数 nCr を求めます。
     * 5!(5*4*3*2*1)
     * /
     * 2!(2*1) *  (5-2)!(3*2*1)
     *
     * @param n
     * @param r
     * @return
     */
    private long getComb(int n, int r) {
        long tmp = 1;
        for (int i = 1; i <= r; i++) {
            tmp *= n - i + 1;
            tmp = mod(tmp);
            tmp *= inv(i);
            tmp = mod(tmp);
        }
        return tmp;
    }

    /**
     * 階乗計算の事前累積和
     * [1, 1, 2, 3, 4, 5, … FACTORIAL_NUM]
     * mod済
     */
    void prepareFact() {
        fact = new long[MAX_FACT];
        Arrays.fill(fact, 0);
        invFact = new long[MAX_FACT];
        Arrays.fill(invFact, 0);
        fact[0] = 1;
        int maxIndex = (int) min(MAX_FACT, (int) MOD);
        for (int i = 1; i < maxIndex; i++) {
            fact[i] = mod(fact[i - 1] * i);
        }
        invFact[maxIndex - 1] = inv(fact[maxIndex - 1]);
        for (int i = maxIndex - 1; i > 0; i--) {
            invFact[i - 1] = mod(invFact[i] * i);
        }
    }

    /**
     * 順列
     * nPk -> n! / (n-k)!
     *
     * @param n
     * @param r
     * @return
     */
    long permutation(int n, int r) {
        if (n < 0 || r < 0 || n < r) {
            return 0;
        }
        return mod(fact[n] * invFact[n - r]);
    }

    /**
     * 組み合わせ
     * nCk -> n! / k!・(n-k)!
     *
     * @param n
     * @param r
     * @return
     */
    long combination(int n, int r) {
        if (n < 0 || r < 0 || n < r) {
            return 0;
        }
        return mod(permutation(n, r) * invFact[r]);
    }

    /**
     * 重複組合せ nHr （同次積）
     * nHr = (n+r-1)Cr
     * 異なるn個のものから重複を許してr個取る組合せの総数
     * 例：
     * リンゴ，ミカン，牛肉の3種類の果物があります．これらの中から6個の食材を買って帰ります．
     * このとき，何通りの買い方がありますか？ただし，含まれない食材があってもよいものとします
     *
     * @param n
     * @param r
     * @return
     */
    long homogeneousProduct(int n, int r) {
        return combination((n - 1) + r, r);
    }

    /**
     * 多項係数
     * 文字aをp個,bをq個,cをr個, dをs個 あわせてn個を1列に並べるときの並べ方
     * n! / p!・q!・r!・s!
     *
     * @param n
     * @param strNum
     * @param mod
     * @return
     */

    /**
     * フェルマーの小定理を用いて逆元を求める。
     * ある数xのmod p（pは素数）の逆数x'はx' = x^(p-2)
     * 繰り返し二乗法を用いて計算する。
     * http://satanic0258.hatenablog.com/entry/2016/04/29/004730
     * {@link BigInteger#modInverse(BigInteger)}とどちらが速いか？
     *
     * @param x
     * @return
     */
    private long modInverse(long x, long mod) {
        long res = 1L;
        long k = mod - 2L;
        long y = x;
        while (k != 0) {
            if (k % 2 != 0) {
                res = (res * y) % mod;
            }
            y = (y * y) % mod;
            k /= 2;
        }
        return res;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
    }

    public boolean hasNext() {
        skipUnprintable();
        return hasNextByte();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public long min(long... v) {
        long min = Long.MAX_VALUE;
        for (long i : v) min = Math.min(min, i);
        return min;
    }

    public long max(long... v) {
        long max = Long.MIN_VALUE;
        for (long i : v) max = Math.max(max, i);
        return max;
    }
}


Measured memory_bytes: 127680