Hərşeyə Qadirlik Plitələri
Lord Benedikt, Qara Hakimin qalasından qaçaraq, birbaşa Qara Qalanın xəzinəsinə daxil olur. Xəzinə, N×N ölçüsündə kvadrat bir otaqdır. Benedikt otağın sol üst küncündədir, çıxış isə sağ alt küncdə yerləşir. Otağın bəzi hüceyrələrində Qüdrət Plitələri var. Benedikt otaqdan çıxmalı və mümkün qədər çox Qüdrət Plitəsindən keçməlidir. O, hamısını ziyarət edə bilərdi, lakin səhərdən bəri "Sürətli Ayaqqabılar" geyindiyi üçün yalnız sağa və ya aşağıya hərəkət edə bilir. Buna görə də, optimal marşrutu seçməlidir.
Giriş verilənləri
Birinci sətirdə N (1 ≤ N ≤ 500) ədədi verilir. Növbəti N sətirdə xəzinəni təsvir edən N ədəd var, sol üst hüceyrədən başlayaraq sağ alt hüceyrəyə qədər. 0 ədədi boş hüceyrəni, 1 ədədi isə Plitəli hüceyrəni göstərir. Sol üst və sağ alt hüceyrələrdə plitələr yoxdur.
Çıxış verilənləri
Benediktin keçə biləcəyi maksimum Qüdrət Plitələrinin sayını çıxarın.