Problem: One day, Hongcow goes to the store and sees a brand new deck of n special cards. Each individual card is either red or blue. He decides he wants to buy them immediately. To do this, he needs to play a game with the owner of the store.

This game takes some number of turns to complete. On a turn, Hongcow may do one of two things: 

  * Collect tokens. Hongcow collects 1 red token and 1 blue token by choosing this option (thus, 2 tokens in total per one operation). 
  * Buy a card. Hongcow chooses some card and spends tokens to purchase it as specified below. 



The i-th card requires ri red resources and bi blue resources. Suppose Hongcow currently has A red cards and B blue cards. Then, the i-th card will require Hongcow to spend max(ri - A, 0) red tokens, and max(bi - B, 0) blue tokens. Note, only tokens disappear, but the cards stay with Hongcow forever. Each card can be bought only once.

Given a description of the cards and their costs determine the minimum number of turns Hongcow needs to purchase all cards.

Input

The first line of input will contain a single integer n (1 ≤ n ≤ 16).

The next n lines of input will contain three tokens ci, ri and bi. ci will be 'R' or 'B', denoting the color of the card as red or blue. ri will be an integer denoting the amount of red resources required to obtain the card, and bi will be an integer denoting the amount of blue resources required to obtain the card (0 ≤ ri, bi ≤ 107).

Output

Output a single integer, denoting the minimum number of turns needed to acquire all the cards.

Examples

Input

3
R 0 1
B 1 0
R 1 1


Output

4


Input

3
R 3 0
R 2 0
R 1 0


Output

6

Note

For the first sample, Hongcow's four moves are as follows: 

  1. Collect tokens 
  2. Buy card 1
  3. Buy card 2
  4. Buy card 3

Note, at the fourth step, Hongcow is able to buy card 3 because Hongcow already has one red and one blue card, so we don't need to collect tokens.

For the second sample, one optimal strategy is as follows: 

  1. Collect tokens 
  2. Collect tokens 
  3. Buy card 2
  4. Collect tokens 
  5. Buy card 3
  6. Buy card 1

At the fifth step, even though Hongcow has a red token, Hongcow doesn't actually need to spend it, since Hongcow has a red card already.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
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
 */
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);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        int n;
        char[] colorCard;
        int[] costRedToken;
        int[] costBlueToken;
        final int inf = (int) 1e9;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.readInt();
            colorCard = new char[n];
            costRedToken = new int[n];
            costBlueToken = new int[n];

            int overRed = 0;
            int overBlue = 0;

            for (int i = 0; i < n; i++) {
                colorCard[i] = in.readCharacter();

                costRedToken[i] = in.readInt();
                costBlueToken[i] = in.readInt();

                overRed += Math.max(costRedToken[i] - n, 0);
                overBlue += Math.max(costBlueToken[i] - n, 0);

                costRedToken[i] = Math.min(n, costRedToken[i]);
                costBlueToken[i] = Math.min(n, costBlueToken[i]);
            }


            int over = Math.max(overRed, overBlue);

            int[][][] dp = new int[2][n * n + 1][1 << n];
            ArrayUtils.fill(dp, inf);

            if (overRed < overBlue) {
                dp[0][Math.min(over - overRed, n * n)][0] = 0;
            } else {
                dp[1][Math.min(over - overBlue, n * n)][0] = 0;
            }

            int sqrN = n * n;

            for (int msk = 0; msk < (1 << n); msk++) {

                int countRedCard = 0;
                int countBlueCard = 0;
                for (int card = 0; card < n; card++) {
                    if (((msk >> card) & 1) == 1) {
                        if (colorCard[card] == 'R') {
                            ++countRedCard;
                        } else if (colorCard[card] == 'B') {
                            ++countBlueCard;
                        } else {
                            throw new RuntimeException();
                        }
                    }
                }

                for (int typeRemToken = 0; typeRemToken < 2; typeRemToken++) {
                    for (int countRemTokens = 0; countRemTokens <= sqrN; countRemTokens++) {

                        int curDP = dp[typeRemToken][countRemTokens][msk];
                        if (curDP == inf) {
                            continue;
                        }

                        for (int card = 0; card < n; card++) {
                            if (((msk >> card) & 1) == 1) {
                                continue;
                            }

                            int countHaveRedToken = typeRemToken == 0 ? countRemTokens : 0;
                            int countHaveBlueToken = typeRemToken == 1 ? countRemTokens : 0;

                            int costRed = Math.max(costRedToken[card] - countRedCard, 0);
                            int costBlue = Math.max(costBlueToken[card] - countBlueCard, 0);

                            int countBuyToken = Math.max(Math.max(costRed - countHaveRedToken, 0), Math.max(costBlue -
                                    countHaveBlueToken, 0));

                            int remRedToken = countBuyToken + countHaveRedToken - costRed;
                            int remBlueToken = countBuyToken + countHaveBlueToken - costBlue;

                            int toMsk = msk | (1 << card);
                            int toTypeRemToken = remRedToken == 0 ? 1 : 0;
                            int toCountRemTokens = Math.min(Math.max(remRedToken, remBlueToken), sqrN);

                            dp[toTypeRemToken][toCountRemTokens][toMsk] = Math.min
                                    (dp[toTypeRemToken][toCountRemTokens][toMsk],
                                            curDP + countBuyToken);

                        }
                    }
                }
            }

            int curAns = inf;
            for (int typeRemToken = 0; typeRemToken < 2; typeRemToken++) {
                for (int countRemTokens = 0; countRemTokens <= n * n; countRemTokens++) {
                    curAns = Math.min(curAns, dp[typeRemToken][countRemTokens][(1 << n) - 1]);
                }
            }
            out.printLine(n + over + curAns);
//        out.printLine(dp[0][1][0b1]);
//        out.printLine(dp[0][1][0b11]);
//        out.printLine(dp[0][1][0b111]);
        }

    }

    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 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 readInt() {
            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 static boolean isWhitespace(int c) {
            return (c == ' ') || (c == '\n') || (c == '\r') || (c == '\t') || (c == -1);
        }

        public char readCharacter() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) 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 printLine(int i) {
            writer.println(i);
        }

    }

    static class ArrayUtils {
        public static void fill(int[][] array, int value) {
            for (int[] row : array) {
                Arrays.fill(row, value);
            }
        }

        public static void fill(int[][][] array, int value) {
            for (int[][] subArray : array) {
                fill(subArray, value);
            }
        }

    }
}