Дима очень любит Инну, поэтому он решил написать ей песню. У Димы есть волшебная гитара, у которой n струн и m ладов. Звукоизвлечение на гитаре происходит следующим образом: чтобы сыграть ноту, нужно зажать одну из струн на одном из ладов, а затем дернуть эту струну. Обозначим ноту, которую играет Димина гитара, если на ней сыграть i-ую струну зажатую на j-ом ладу, переменной a_ij. Известно, что Димина гитара может играть k различных нот, при этом вполне вероятно, что некоторые ноты можно сыграть несколькими способами. Другими словами, возможно, a_ij = a_pq при (i, j) ≠ (p, q).

Дима уже написал песню — последовательность из s нот. Чтобы сыграть песню нужно последовательно сыграть ноты из песни на гитаре, причем каждую ноту можно играть любым из доступных способов. Дима понял, что есть очень много способов сыграть песню, и хочет сыграть ее так, чтобы она выглядела как можно сложнее (выкобеЙнивается).

Будем обозначать способ сыграть песню последовательностью пар (x_i, y_i) (1 ≤ i ≤ s) таких, что x_i-ая струна на y_i-ом ладу издает i-ую ноту песни. Сложностью перехода между парами (x₁, y₁) и (x₂, y₂) назовем значение + . Сложностью способа сыграть песню назовем максимальную из сложностей переходов между соседними парами в способе.

Помогите Диме определить максимально возможную сложность способа сыграть его песню! Пусть парень выглядит круто!