Задається ціле число \(N\). Розглянемо трикутник чисел з \(N\) рядків, у якому в першому рядку міститься \(a_{11}\), у другому рядку -- два числа \(a_{21}\) і \(a_{22}\), у третьому -- три числа \(a_{31}\), \(a_{32}\) і \(a_{33}\), і т.д.

Складіть програму, яка обчислюватиме найбільшу із сум чисел, які з'являються на шляхах, починаючи зверху до основи, так що: на кожному шляху наступне число знаходиться в рядку нижче, точніше, безпосередньо під попереднім числом або нижче і на одне місце праворуч.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(1 \le N \le 100\)).

Наступні \(N\) рядків містять цілі числа згідно формату: перший рядок містить одне число, другий - два, третій - три, і в кінці, \(N\)-й рядок містить \(N\) цілих чисел \(a_{ij}\) (\(0 \le a_{ij} \le 100\)). Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть максимальну суму на окремому із шляхів.

Примітка

До прикладу 1:

Всього 4 шляхи:

• (1,1)→(2,1)→(3,1) із сумою, що дорівнює 4.

• (1,1)→(2,1)→(3,2) із сумою, рівною 5

• (1,1)→(2,2)→(3,2) із сумою, рівною 4

• (1,1)→(2,2)→(3,3) із сумою, рівною 5

Отже, максимальна сума дорівнює 5.

Приклад вхідних даних

3
1
2 1
1 2 3

Приклад вихідних даних

5

Приклад вхідних даних

4
1
1 2
4 1 2
2 3 1 1

Приклад вихідних даних

9