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.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		InputReader in = new InputReader(inputStream);
		//InputStream uinputStream = new FileInputStream("teleport.in");
		//InputReader in = new InputReader(uinputStream);
		//PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("teleport.out")));
		Task t = new Task();
		t.solve(in, out);
		out.close();
	}
	
	static class Task {
		public void solve(InputReader in, PrintWriter out) throws IOException {
			int n = in.nextInt();
			ArrayList<Integer> edge[] = new ArrayList[16];
			for(int i=0;i<16;i++) edge[i] = new ArrayList<Integer>();
			for(int i=0;i<n;i++) {
				int f = in.nextInt();
				int v = in.nextInt();
				int t = in.nextInt();
				f--;t--;
				edge[ID(f,t)].add(v);
			}
			
			for(int i=0;i<16;i++) {
				Collections.sort(edge[i]);
			}
			long max = 0;
			for(int i=0;i<4;i++) {
				int tmp[] = new int[16];
				for(int j=0;j<16;j++) {
					tmp[j] = edge[j].size()-1;
				}
				max = Math.max(max, dfs(i,tmp,edge));
			}
//			int g[][][] = new int[5][5][n+1];
//			for(int i=0;i<n;i++) {
//				int f = in.nextInt();
//				int v = in.nextInt();
//				int t = in.nextInt();
//				if(f==t) {
//					g[f][f][0]++;
//					g[f][f][g[f][f][0]] = v;
//				}else {					
//					g[f][t][0]++;
//					g[f][t][g[f][t][0]] = v;					
//					g[t][f][0]++;
//					g[t][f][g[t][f][0]] = v;					
//				}
//			}
//			for(int i=1;i<=4;i++) {
//				for(int j=1;j<=4;j++) {
//					Arrays.sort(g[i][j], 1, g[i][j][0]+1);
//				}
//			}
//			long max = 0;
//			for(int i=1;i<=4;i++) {
//				int copy[][][] = new int[5][5][n+1];
//				for(int ii=0;ii<5;ii++) {
//					for(int j=0;j<5;j++) {
//						for(int k=0;k<=g[ii][j][0];k++) copy[ii][j][k] = g[ii][j][k];
//					}
//				}
//				long t = dfs(i,copy);
//				Dumper.print(t);
//				max = Math.max(max, t);
//			}
			out.println(max);
		}
		int ID(int x, int y) {
			if(x>y) {
				int tmp=x;
				x=y;
				y=tmp;
			}
			return x*4+y;
		}	
		long dfs(int cur, int[] co, ArrayList<Integer>[] edge) {
			int t[] = new int[16];
			for(int i=0;i<16;i++) t[i] = co[i];
			long ret = 0;
			for(int i=0;i<4;i++) {
				int id = ID(cur,i);
				if(i==cur) while(t[id]>=0) ret+=edge[id].get(t[id]--);
				else while(t[id]>2) ret+=edge[id].get(t[id]--)+edge[id].get(t[id]--);
			}
			long max = ret;
			for(int i=0;i<4;i++) {
				int id = ID(cur,i);
				if(t[id]>=0) {
					t[id]--;
					max = Math.max(max, ret+dfs(i,t,edge)+edge[id].get(t[id]+1));
					t[id]++;
				}
			}
			return max;
		}
//		long dfs(int cur, int g[][][]) {
//			int num = 0;
//			for(int i=0;i<5;i++) {
//				for(int j=0;j<5;j++) {
//					if(g[i][j][0]!=0) num++;
//				}
//			}
//			if(num==1) {
//				Dumper.print("here");
//			}
//			long ret = 0;
//			for(int i=1;i<=4;i++) {
//				if(i==cur) {
//					while(g[cur][i][0]>0) {
//						ret+=g[cur][i][g[cur][i][0]--];				
//					}
//				}else {
//					while(g[cur][i][0]>4) {
//						ret+=g[cur][i][g[cur][i][0]--];
//						g[i][cur][0]--;
//						ret+=g[cur][i][g[cur][i][0]--];
//						g[i][cur][0]--;
//					}
//				}
//			}
//			long max = ret;
//			for(int i=1;i<=4;i++) {
//				if(g[cur][i][0]==0) continue;
//				g[cur][i][0]--;
//				g[i][cur][0]--;
//				long tmp = ret+dfs(i,g)+g[cur][i][g[cur][i][0]+1];
//				//Dumper.print(cur+"^"+i+"^"+tmp);
//				max = Math.max(tmp, max);
//				g[cur][i][0]++;
//				g[i][cur][0]++;
//			}
//			return max;
//		}
	}
	
	static class MinHeap<Key> implements Iterable<Key> {
		private int maxN;
		private int n;
		private int[] pq;
		private int[] qp;
		private Key[] keys;
		private Comparator<Key> comparator;
		
		public MinHeap(int capacity){
			if (capacity < 0) throw new IllegalArgumentException();
			this.maxN = capacity;
			n=0;
			pq = new int[maxN+1];
			qp = new int[maxN+1];
			keys = (Key[]) new Object[capacity+1];
			Arrays.fill(qp, -1);
		}
		
		public MinHeap(int capacity, Comparator<Key> c){
			if (capacity < 0) throw new IllegalArgumentException();
			this.maxN = capacity;
			n=0;
			pq = new int[maxN+1];
			qp = new int[maxN+1];
			keys = (Key[]) new Object[capacity+1];
			Arrays.fill(qp, -1);
			comparator = c;
		}			
		public boolean isEmpty()	{ return n==0; 	}
		public int size()			{ return n;		}
		public boolean contains(int i) {
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        return qp[i] != -1;
		}	
		public int peekIdx() {
	        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
	        return pq[1];		
		}	
		public Key peek(){
			if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
			return keys[pq[1]];
		}
		public int poll(){
			if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
			int min = pq[1];
			exch(1,n--);
			down(1);
			assert min==pq[n+1];
			qp[min] = -1;
			keys[min] = null;		
			pq[n+1] = -1;
			return min;
		}
	    public void update(int i, Key key) {
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        if (!contains(i)) {
	        	this.add(i, key);
	        }else {
	        	keys[i] = key;
	        	up(qp[i]);
	        	down(qp[i]);
	        }
	    }	
		private void add(int i, Key x){
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
	        n++;
	        qp[i] = n;
	        pq[n] = i;
	        keys[i] = x;
	        up(n);
		}
		private void up(int k){
			while(k>1&&less(k,k/2)){
				exch(k,k/2);
				k/=2;
			}
		}
		private void down(int k){
			while(2*k<=n){
				int j=2*k;
				if(j<n&&less(j+1,j)) j++;
				if(less(k,j)) break;
				exch(k,j);
				k=j;
			}
		}
		
		public boolean less(int i, int j){
	        if (comparator == null) {
	            return ((Comparable<Key>) keys[pq[i]]).compareTo(keys[pq[j]]) < 0;
	        }
	        else {
	            return comparator.compare(keys[pq[i]], keys[pq[j]]) < 0;
	        }
		}

		public void exch(int i, int j){
	        int swap = pq[i];
	        pq[i] = pq[j];
	        pq[j] = swap;
	        qp[pq[i]] = i;
	        qp[pq[j]] = j;
		}

		@Override
		public Iterator<Key> iterator() {
			// TODO Auto-generated method stub
			return null;
		}
	}  	

    private static class InputReader
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int zcurChar;
        private int znumChars;
        private SpaceCharFilter filter;

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

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

        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 String nextString()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do
            {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public double nextDouble()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.')
            {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.')
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public long nextLong()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long 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 c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next()
        {
            return nextString();
        }

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

	static class Dumper {
		static void print_int_arr(int[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_char_arr(char[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_double_arr(double[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_2d_arr(int[][] arr, int x, int y) {
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_2d_arr(boolean[][] arr, int x, int y) {
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print(Object o) {
			System.out.println(o.toString());
		}

		static void getc() {
			System.out.println("here");
		}
	}
}
