Stepanın İrsi

Stepan babasından n yerdən ibarət, 1-dən n-ə qədər nömrələnmiş bir dayanacaq miras alıb. Dayanacaq iki hissəyə bölünüb: ilk m yer sol tərəfdə, qalan n - m yer isə sağ tərəfdədir. Hər gün bu məhəllənin n sakini avtomobillərini Stepanın dayanacağında park edir. Məlumdur ki, birinci sakin hamıdan əvvəl gəlir, sonra ikinci və s., yəni k-cı sakin k-cı gəlir. Həmçinin, hər bir i-ci sakin üçün onun avtomobilini j-ci yerə qoyduqda nə qədər ödəyəcəyi məlumdur. Stepan hər bir gələn avtomobilə hansı tərəfdə park etməli olduğunu göstərən bir yer paylayıcısı aldı, bundan sonra avtomobil müvafiq tərəfdəki ən kiçik nömrəli boş yerə park edir. Bununla belə, Stepan qənaət etmək qərarına gəldi və paylayıcı üçün proqram təminatı almadı, buna görə də o, optimal işləmir.

Stepan sizdən bu paylayıcı üçün Stepanın gəlirlərini maksimuma çatdıracaq bir proqram yazmağı xahiş edir.

Giriş məlumatları

Birinci sətirdə dayanacaqda ümumi yer sayı və sol tərəfdəki yerlərin sayı olmaqla iki tam ədəd n (2 ≤ n ≤ 1000) və m (1 ≤ m < n) verilir. Növbəti n sətirdə hər biri n müsbət tam ədəd olmaqla yazılmışdır. i-ci sətirdəki j-ci ədəd, i-ci sakinin bu dayanacaqda j nömrəli yer üçün nə qədər ödəyəcəyini göstərir. Bu ədədlərin hər biri 10^6-dan çox deyil.

Çıxış məlumatları

Bir ədəd çıxarın - dayanacağın maksimal gəliri.