시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Dane są dwa ciągi znaków X i Y, składające się z liter 'a','b' i 'c'. Należy znaleźć najdłuższy niemalejący wspólny podciąg ciągów X i Y. Inaczej mówiąc, należy znaleźć najdłuższy ciąg, który:

  • jest podciągiem ciągów X i Y, czyli da się go otrzymać przez usunięcie pewnych liter z ciągów X i Y;
  • jest niemalejący pod względem kolejności liter w alfabecie, czyli przed wystąpieniem litery v nie wystąpi litera o większym kodzie ASCII niż v.

입력

W pierwszej linii znajdują się dwie liczby całkowite n i m (1 ≤ n, m ≤ 200 000), oznaczające długości ciągów X i Y. W drugiej linii znajduje się ciąg X, a w następnej Y.

출력

W pierwszym wierszu należy wypisać długość najdłuższego ciągu spełniającego warunki zadania.

예제 입력 1

5 6
cabbc
bacbcc

예제 출력 1

3

힌트

Najdłuższy ciąg spełniający warunki zadania to "abc".