Nazirlik

Cənab F. sənədi nazirə imzalatmaq istəyir. Nazir sənədi yalnız onun nazirliyi tərəfindən təsdiqləndiyi halda imzalayacaq. Nazirlik M mərtəbəli bir binadır, mərtəbələr 1 -dən M -ə qədər nömrələnmişdir (1 ≤ M ≤ 100). Hər mərtəbədə N otaq var (1 ≤ N ≤ 500), otaqlar 1 -dən N -ə qədər nömrələnmişdir. Hər otaqda bir (və yalnız bir) məmur var.

Sənəd nazirlik tərəfindən təsdiqlənmiş sayılır, əgər o, M-ci mərtəbədən ən azı bir məmur tərəfindən imzalanıbsa. Məmur sənədi imzalayır, əgər aşağıdakı şərtlərdən ən azı biri yerinə yetirilirsə:

• məmur 1-ci mərtəbədə işləyir;

• sənəd eyni nömrəli otaqda, lakin aşağı mərtəbədə olan məmur tərəfindən imzalanıbsa;

• sənəd qonşu otaqdan olan məmur tərəfindən imzalanıbsa (otaqlar qonşu sayılır, əgər onlar eyni mərtəbədə yerləşir və otaq nömrələri bir vahid fərqlənirsə).

Hər məmur sənədi imzalamaq üçün ödəniş alır. Ödəniş 10^9 -u keçməyən təbii ədəddir. Sənədi imzalamaq üçün ən ucuz yolu tapın.

Giriş verilənləri

Birinci sətir binadakı mərtəbələrin sayı M və mərtəbədəki otaqların sayı N göstərir. Növbəti M sətirin hər biri məmurların ödənişlərini təsvir edən N ədəd ehtiva edir (k-cı ədəd l-ci sətirdə k-cı otaqda l-ci mərtəbədə oturan məmurun ödənişini göstərir).

Çıxış verilənləri

Sənədi minimal ödənişlə imzalamaq üçün otaqların nömrələrini ziyarət sırasına görə çıxarın. Əgər belə imzalama yolları bir neçə varsa, onlardan hər hansı birini çıxarın.