Stansiyalar
Çox Böyük Dəmir Yolu (ÇBDY) yeni gediş haqqı sistemini tətbiq etməyə qərar verib. ÇBDY düz xətt boyunca ardıcıl yerləşdirilmiş N stansiyadan ibarətdir. Bu stansiyalar M ardıcıl zonaya bölünəcək, elə ki, hər zona ən azı bir stansiya ehtiva etsin. Stansiya i-dən stansiya k-yə gediş haqqı 1+|z_i−z_k| olaraq təyin edilir, burada z_i və z_k stansiya i və k-nın aid olduğu zonaların nömrələridir.
Hər bir stansiyadan digərinə gün ərzində gedən sərnişinlərin sayı məlumdur. Yeni sistemə əsasən zonaların optimal bölünməsi ilə əldə edilə biləcək maksimum günlük gəliri müəyyən edən bir proqram yazın.
Giriş verilənləri
Proqram standart girişdən N sətir oxuyur. Birinci sətir iki tam ədəd N və M (1≤M≤N≤1000) ehtiva edir. İkinci sətir stansiya 1-dən stansiya 2-yə gedən sərnişinlərin sayını göstərən bir ədəd ehtiva edir. Üçüncü sətir stansiya 1-dən stansiya 3-ə və stansiya 2-dən stansiya 3-ə gedən sərnişinlərin sayını göstərən iki ədəd ehtiva edir. Beləliklə, N-ci sətir N−1 ədəd ehtiva edir, i-ci ədəd stansiya i-dən stansiya N-ə gedən sərnişinlərin sayını müəyyən edir. Hər bir stansiya cütü üçün sərnişin sayı hər iki istiqamətdə nəzərə alınır. Bütün ədədlər tam, qeyri-mənfi və 10000-dən çox deyil.
Çıxış verilənləri
Proqram standart çıxışa tək tam ədəd - axtarılan maksimum günlük gəliri çıxarmalıdır.