تأمل مثلث الأعداد أدناه. اكتب برنامجا يحسب أكبر مجموع للأعداد التي يمر بها مسار يبدأ من القمة وينتهي في موضع ما على القاعدة. كل خطوة تتجه قطريا إلى أسفل اليسار أو أسفل اليمين.

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

في المثال، المسار عبر 7 ثم 3 ثم 8 ثم 7 ثم 5 يعطي أكبر مجموع: 30.

الإدخال

يحتوي السطر الأول على عدد الصفوف $R$ ($1 \le R \le 1000$). يحتوي كل سطر تال على أعداد صف المثلث المقابل. جميع الأعداد صحيحة غير سالبة ولا تتجاوز 100.

الإخراج

سطر واحد يحتوي أكبر مجموع وفقا للاجتياز المحدد.

أمثلة

الإدخال 1

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

الإخراج 1

30