You are given n blocks, each of them is of the form [color_1|value|color_2], where the block can also be flipped to get [color_2|value|color_1]. 

A sequence of blocks is called valid if the touching endpoints of neighboring blocks have the same color. For example, the sequence of three blocks A, B and C is valid if the left color of the B is the same as the right color of the A and the right color of the B is the same as the left color of C.

The value of the sequence is defined as the sum of the values of the blocks in this sequence.

Find the maximum possible value of the valid sequence that can be constructed from the subset of the given blocks. The blocks from the subset can be reordered and flipped if necessary. Each block can be used at most once in the sequence.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 100) — the number of given blocks.

Each of the following n lines describes corresponding block and consists of color_{1,i}, value_i and color_{2,i} (1 ≤ color_{1,i}, color_{2,i} ≤ 4, 1 ≤ value_i ≤ 100 000).

Output

Print exactly one integer — the maximum total value of the subset of blocks, which makes a valid sequence.

Examples

Input

6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2


Output

63

Input

7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3


Output

300000

Input

4
1 1000 1
2 500 2
3 250 3
4 125 4


Output

1000

Note

In the first example, it is possible to form a valid sequence from all blocks.

One of the valid sequences is the following:

[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2]

The first block from the input ([2|1|4] → [4|1|2]) and second ([1|2|4] → [4|2|1]) are flipped.

In the second example, the optimal answers can be formed from the first three blocks as in the following (the second or the third block from the input is flipped):

[2|100000|1] [1|100000|1] [1|100000|2]

In the third example, it is not possible to form a valid sequence of two or more blocks, so the answer is a sequence consisting only of the first block since it is the block with the largest value.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author prakharjain
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        _1038E solver = new _1038E();
        solver.solve(1, in, out);
        out.close();
    }

    static class _1038E {
        long ans = 0;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            PriorityQueue[][] l = new PriorityQueue[4][4];

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    l[i][j] = new PriorityQueue<Integer>((x, y) -> y - x);
                }
            }

            for (int i = 0; i < n; i++) {
                int c1 = in.nextInt() - 1;
                int v = in.nextInt();
                int c2 = in.nextInt() - 1;

                if (c1 > c2) {
                    int t = c1;
                    c1 = c2;
                    c2 = t;
                }

                l[c1][c2].add(v);
            }

            NextPermutation np = new NextPermutation();

            int[] a = new int[8];

            for (int i = 0; i < 8; i++) {
                a[i] = i + 1;
            }


            do {

                int[] b = new int[8];

                for (int i = 0; i < 8; i++) {
                    b[i] = a[i] - 1;

                    if (b[i] >= 4) {
                        b[i] -= 4;
                    }
                }

                for (int i = 0; i < 8; i++) {
                    process(0, i, b, l);
                }

            } while ((a = np.nextPermutation(a)) != null);

            out.print(ans);
        }

        void process(int s, int e, int[] a, PriorityQueue[][] pq) {
            PriorityQueue[][] pq2 = new PriorityQueue[4][4];

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (i <= j)
                        pq2[i][j] = new PriorityQueue(pq[i][j]);
                    else
                        pq2[i][j] = pq2[j][i];
                }
            }

            long ca = 0;
            int re = s;
            for (int i = s; i <= e; i++) {
                int cv = a[i];
                while (pq2[cv][cv].size() > 0) {
                    ca += (int) pq2[cv][cv].poll();
                }
                re = i;
                if (i < e) {
                    int nv = a[i + 1];
                    if (pq2[cv][nv].size() > 0) {
                        ca += (int) pq2[cv][nv].poll();
                    } else {
                        break;
                    }
                }
            }

            for (int i = s; i <= re; i++) {
                int cv = a[i];
                for (int j = 0; j < 4; j++) {
                    while (pq2[cv][j].size() >= 2) {
                        ca += (int) pq2[cv][j].poll();
                        ca += (int) pq2[cv][j].poll();
                    }
                }
            }

            ans = Math.max(ans, ca);
        }

        class NextPermutation {
            public int[] nextPermutation(int[] nums) {
                if (nums == null || nums.length < 2)
                    return null;

                int p = 0;
                for (int i = nums.length - 2; i >= 0; i--) {
                    if (nums[i] < nums[i + 1]) {
                        p = i;
                        break;
                    }
                }

                int q = 0;
                for (int i = nums.length - 1; i > p; i--) {
                    if (nums[i] > nums[p]) {
                        q = i;
                        break;
                    }
                }

                if (p == 0 && q == 0) {
                    reverse(nums, 0, nums.length - 1);
                    return null;
                }

                int temp = nums[p];
                nums[p] = nums[q];
                nums[q] = temp;

                if (p < nums.length - 1) {
                    reverse(nums, p + 1, nums.length - 1);
                }

                return nums;
            }

            public void reverse(int[] nums, int left, int right) {
                while (left < right) {
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    left++;
                    right--;
                }
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void print(long i) {
            writer.print(i);
        }

    }
}

