Question

Increasing Subsequence with Largest Sum


Given a sequence a1, a2, ..... an, of positive integers, a strictly increasing subsequence is a subsequence of the given sequence such that each term of the subsequence is strictly less than the next. For example, in the sequence 1, 2, 10, 3, 7 , 4, two strictly increasing sub sequences are 1, 10 and 2, 3, 4

The Input consists of N sets of five integers each. From these sets, a derived sequence is formed by selecting one of the five numbers in each set as part of the sequence.

The objective is to pick the numbers from each set so that the corresponding derived sequence has the strictly increasing subsequence with the largest sum.

Input

The first line of the input has a positive integer N which is the number of sets of the numbers in the input. Each of the next N lines consists of a set of five (not necessarily distinct) comma separated positive integers.

Output

The sum of the elements of the longest strictly increasing subsequence in all possible derived sequences

Constraints

N<=50

Integers in sets<=10000

Example 1

Input:
5
3000,400,1500,4350,2700
2050,3650,650,2750,4300
2000,700,2100,700,1650
300,200,500,600,200
3000,3100,3200,1100,1400

Output:
8850

Explanation:
A possible derived sequence from the input which gives the maximum sum for a strictly increasing subsequence is 1500,2050,2100,500,3200 (one from each row), and the strictly increasing subsequence that gives the maximum sum from this from this is 1500,2050,2100,3200, whose sum is 8850, which is the output

Example 2

Input:
6 800,3000,600,3600,800
1400,5200,1600,6000,2600
3200,3800,3200,1600,2400
800,2800,4800,600,1400
5200,1400,4800,3800,800
5000,4200,4800,1800,2000

Output:
17400

Explanation:
A possible derived sequence that gives a maximum sum for a strictly increasing subsequence is 800, 1600, 2400, 2800, 4800, 5000. All appear in the strictly increasing subsequence, and the sum is 17400, which is the output

Answer 1

class Main2{  public static void main(String[] arg) throws Exception{ java.util.Scanner scanner = new java.util.Scanner(System.in);  int n = scanner.nextInt();  char c;  int[][] arr = new int[n+1][5];  for(int i = 0; i < n+1; i++){     String line = scanner.nextLine(); //System.out.println(line); if(!line.equals("")) {     String[] line1 = line.split(",");// System.out.println(line1);     for(int j = 0 ; j < line1.length; j++){ //System.out.println(line1[j]);      arr[i-1][j] = Integer.parseInt(line1[j]); }}  }      for(int i = 0; i < n+1; i++){ for(int j = 0; j < 5; j++){ for(int k = 0; k < 5; k++){ if(arr[i][j] <arr[i][k]){ int temp = arr[i][j]; arr[i][j] = arr[i][k]; arr[i][k] = temp; } } }  }    /*for(int i = 0; i < n+1; i++){ for(int j = 0; j < 5; j++){ System.out.println(arr[i][j]); } }*/      int[] sum = new int[n+1];  sum[0] = arr[n][4];  int max = arr[n][4];int p = 1;
for(int i=n-1;i>=0;i--){ for(int j =4;j>=0;j--) { if(arr[i][j]<max) { max =arr[i][j]; sum[p]=arr[i][j]; //System.out.println(max); break; } } if(sum[p]==0) { sum[p-1]=arr[i][4]; max = sum[p-1]; } p++;}  /*for(int i =0 ;i<n;i++){ for(int j =0;j<5;j++) { System.out.println(arr[i][j]); }

}*///System.out.println();int val=0;for(int i=0;i<n+1;i++){System.out.println(sum[i]); val = val+sum[i];} System.out.println(val);}

}