<image>


Arrange integers (0 or more and 99 or less) in a rhombus as illustrated in Fig. 1. Create a program that reads the data representing the rhombus and outputs the maximum value of the sum of the integers that pass when starting from the top and proceeding to the bottom according to the following rules.

* At each step, you can proceed to the lower left diagonal or the lower right diagonal.



For example, in the example of Fig. 1, as shown in Fig. 2, when 7,3,8,7,5,7,8,3,7 is selected and passed, the sum is the maximum 55 (7 + 3 + 8). + 7 + 5 + 7 + 8 + 3 + 7 = 55).



Input

As shown in the input example, a comma-separated sequence of integers is given to the diamond. Each line does not contain whitespace. The input example corresponds to Fig. 1. There are less than 100 rows of data.

Output

Outputs the maximum value of the sum of integers that pass according to the rules on one line.

Example

Input

7
3,8
8,1,0
2,7,4,4
4,5,2,6,5
2,7,4,4
8,1,0
3,8
7


Output

55

import java.io.*;
import java.util.*;


// 2011/10/23

// 0089 Ðµ`
public class Main {

	// C return falseÅ¨µÜ¢
	boolean main() throws IOException {

		List<int[]> list = new ArrayList<int[]>();
		
		int size = 0;
		for(int i = 0;; i++) {
			if (size != 0 && i >= size * 2 - 1)
				break;
			int[] ia = readIntArray();
			list.add(ia);
			if (size == 0 && ia.length < i + 1)
				size = i;
		}
		

		int[] prevLine = new int[] { list.get(0)[0] };
		
		for(int y = 1; y < size * 2 - 1; y++) {
			
			int xSize = y + 1;
			if (y >= size) {
				xSize = size * 2 -1 - y;
			}
			log.printf("xSize=%d\n", xSize); 
			int[] line = new int[xSize];
			for(int x = 0; x < xSize; x++) {
				int max = 0;
				if (y < size) { // O¼
					if (x - 1 >= 0) {
						max = prevLine[x - 1];
					}
					if (x < prevLine.length) {
						max = Math.max(max, prevLine[x]);
					}
				}
				else { // ã¼
					if (x >= 0) {
						max = prevLine[x];
					}
					if (x + 1 < prevLine.length) {
						max = Math.max(max, prevLine[x + 1]);
					}
				}
				max += list.get(y)[x];
				line[x] = max;
				log.printf("%d ", max);
			}
			log.printf("\n");
			
			prevLine = line;
		}
		
			
		// ðÌ\¦
		System.out.printf("%d\n", prevLine[0]);
		
		
		return false;
		//return true; // ³íI¹ Ö
	}
	

//	private final static boolean DEBUG = true;  // debug
	private final static boolean DEBUG = false; // release

	public static void main(String[] args) throws IOException {

		if (DEBUG) {
			log = System.out;
			
			String inputStr = "7:3,8:8,1,0:2,7,4,4:4,5,2,6,5:2,7,4,4:8,1,0:3,8:7:";

			inputStr = inputStr.replace(":", "\n");

			reader = new BufferedReader(new StringReader(inputStr)); 

		}
		else {
			log = new PrintStream(new OutputStream() { public void write(int b) {} } ); // «ÌÄ
			reader = new BufferedReader(new InputStreamReader(System.in)); // R\[©ç
		}
		
		//int N = readIntArray()[0];

		for(int i = 0; /*i < N*/; i++) {
			boolean b = new Main().main();
			if (!b)
				break;
		}		
		
		reader.close();
	}

	
	static PrintStream log;
	static BufferedReader reader;
	

	// WüÍæè1sªÌæØè¶æØèÅÌ®lðÇÞ
	// EOFÌêÍnullðÔ·
	private static int[] readIntArray() throws IOException {

		String s = null;
		for(;;) {
			s = reader.readLine();
			log.printf("%s\n", s);
			if (s == null)
				return null;
			s = s.trim();
			if (s.length() != 0) // ¦¦¦@Ç¤àËRósðÇÞ±Æª éBÇÝòÎ·Æ¤Ü­¢­çµ¢BBBB
				break;
		}
		
		String[] sp = s.split("[ ,]"); // æØè¶ÍXy[X©J}
		int[] a = new int[sp.length];
		for(int i = 0; i < sp.length; i++) {
			a[i] = Integer.parseInt(sp[i]);
		}
		return a;
	}
		
}