You are appointed director of a famous concert hall, to save it from bankruptcy. The hall is very popular, and receives many requests to use its two fine rooms, but unfortunately the previous director was not very efficient, and it has been losing money for many years. The two rooms are of the same size and arrangement. Therefore, each applicant wishing to hold a concert asks for a room without specifying which. Each room can be used for only one concert per day.

In order to make more money, you have decided to abandon the previous fixed price policy, and rather let applicants specify the price they are ready to pay. Each application shall specify a period [i, j] and an asking price w, where i and j are respectively the first and last days of the period (1 ≤ i ≤ j ≤ 365), and w is a positive integer in yen, indicating the amount the applicant is willing to pay to use a room for the whole period.

You have received applications for the next year, and you should now choose the applications you will accept. Each application should be either accepted for its whole period or completely rejected. Each concert should use the same room during the whole applied period.

Considering the dire economic situation of the concert hall, artistic quality is to be ignored, and you should just try to maximize the total income for the whole year by accepting the most profitable applications.



Input

The input has multiple data sets, each starting with a line consisting of a single integer n, the number of applications in the data set. Then, it is followed by n lines, each of which represents one application with a period [i, j] and an asking price w yen in the following format.


i j w


A line containing a single zero indicates the end of the input.

The maximum number of applications in a data set is one thousand, and the maximum asking price is one million yen.

Output

For each data set, print a single line containing an integer, the maximum total income in yen for the data set.

Example

Input

4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640
0


Output

30
25500
38595
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
  private static class Task {
    void solve(FastScanner in, PrintWriter out) {
      while (true) {
        int N = in.nextInt();
        if (N == 0) break;

        int INF = (int) 1e6;
        MinimumCostFlow flow = new MinimumCostFlow(366);
        for (int i = 0; i < N; i++) {
          int u = in.nextInt() - 1, v = in.nextInt() - 1, w = in.nextInt();
          flow.addEdge(u, v + 1, 1, INF * (v + 1 - u) - w);
        }
        for (int i = 0; i < 365; i++) {
          flow.addEdge(i, i + 1, 2, INF);
        }
        out.println(INF * 2 * 365 - flow.run(0, 365, 2));
      }
    }
  }

  static class MinimumCostFlow {
    class Edge {
      int to, rev;
      long cap, cost;
      Edge(int to, long cap, long cost, int rev) {
        this.to = to;
        this.cap = cap;
        this.cost = cost;
        this.rev = rev;
      }
    }

    private static final long INF = Long.MAX_VALUE / 2;
    private ArrayList<ArrayList<Edge>> G;
    private int V;
    long[] potential;
    long[] dist;
    int[] prevV, prevE;

    MinimumCostFlow(int V) {
      this.V = V;
      G = new ArrayList<>(V);
      for (int i = 0; i < V; i++) G.add(new ArrayList<Edge>());
      potential = new long[V];
      dist = new long[V];
      prevE = new int[V];
      prevV = new int[V];
    }

    void addEdge(int from, int to, long cap, long cost) {
      G.get(from).add(new Edge(to, cap, cost, G.get(to).size()));
      G.get(to).add(new Edge(from, 0, -cost, G.get(from).size() - 1));
    }

    long run(int s, int t, long flow) {
      long cost = 0;
      Arrays.fill(potential, 0);
      while (flow > 0) {
        PriorityQueue<long[]> queue = new PriorityQueue<>(new Comparator<long[]>() {
          @Override
          public int compare(long[] o1, long[] o2) {
            return Long.compare(o1[0], o2[0]);
          }
        });
        Arrays.fill(dist, INF);
        dist[s] = 0;
        queue.add(new long[]{0, s});
        while (!queue.isEmpty()) {
          long[] p = queue.poll();
          int v = (int) p[1];
          if (dist[v] < p[0]) continue;
          for (int i = 0; i < G.get(v).size(); i++) {
            Edge e = G.get(v).get(i);
            int u = e.to;
            if (e.cap > 0 && dist[u] > dist[v] + e.cost + potential[v] - potential[u]) {
              dist[u] = dist[v] + e.cost + potential[v] - potential[u];
              prevV[u] = v;
              prevE[u] = i;
              queue.add(new long[]{dist[u], u});
            }
          }
        }
        if (dist[t] == INF) return -1;
        for (int v = 0; v < V; v++) potential[v] += dist[v];

        long d = flow;
        for (int v = t; v != s; v = prevV[v]) d = Math.min(d, G.get(prevV[v]).get(prevE[v]).cap);
        flow -= d;
        cost += d * potential[t];
        for (int v = t; v != s; v = prevV[v]) {
          Edge e = G.get(prevV[v]).get(prevE[v]);
          e.cap -= d;
          G.get(v).get(e.rev).cap += d;
        }
      }
      return cost;
    }
  }

  // Template
  public static void main(String[] args) {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 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++;
    }

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

    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();
    }

    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();
      }
    }

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

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextInt();
      }
      return array;
    }
  }
}