pub use self::template::*;
use sticky::solve_one_infty;
mod sticky {
    use crate::sticky::permutation::StickyPermutation;
    use std::iter::IntoIterator;
    use std::mem::replace;
    use std::mem::swap;
    use std::ops::{Add, Index, Mul};
    mod permutation {
        use crate::sticky::permutation::steady_ant::steady_ant;
        use self::knuth::{knuth_tropical_multiplication, Core};
        use std::iter::{FromIterator, IntoIterator};
        use std::ops::{Add, Index};
        mod knuth {
            use super::StickyPermutation;
            use std::ops::Index;
            #[derive(Default, Debug, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
            pub struct Core(Vec<Vec<usize>>);
            impl Core {
                pub fn first(&self) -> Option<&Vec<usize>> {
                    self.0.first()
                }
            }
            impl Core {
                pub fn len(&self) -> usize {
                    self.0.len()
                }
                pub fn is_empty(&self) -> bool {
                    self.0.is_empty()
                }
            }
            impl Index<usize> for Core {
                type Output = Vec<usize>;
                fn index(&self, index: usize) -> &Self::Output {
                    &self.0[index]
                }
            }
            impl From<&Core> for StickyPermutation {
                fn from(core: &Core) -> Self {
                    assert!(!core.is_empty());
                    let mut perm = vec![usize::MAX; core.len() - 1];
                    for i in 0..perm.len() {
                        for j in 0..perm.len() {
                            if core[i][j + 1] == core[i][j] + 1
                                && core[i + 1][j + 1] == core[i][j]
                                && core[i + 1][j] == core[i][j]
                            {
                                perm[i] = j;
                            }
                        }
                    }
                    debug_assert!(!perm.contains(&usize::MAX));
                    let ans = Self { perm };
                    debug_assert!(ans.is_valid());
                    ans
                }
            }
            impl From<&StickyPermutation> for Core {
                fn from(perm: &StickyPermutation) -> Self {
                    let mut ans = vec![Vec::default(); perm.len() + 1];
                    *ans.last_mut().unwrap() = vec![0; perm.len() + 1];
                    for i in (0..perm.len()).rev() {
                        ans[i] = ans[i + 1].clone();
                        for j in &mut ans[i][perm[i] + 1..] {
                            *j += 1;
                        }
                    }
                    let ans = Core(ans);
                    debug_assert_eq!(*perm, StickyPermutation::from(&ans));
                    ans
                }
            }
            pub fn knuth_tropical_multiplication(a: &Core, b: &Core) -> Core {
                let rows = a.len();
                let cols = match b.first() {
                    None => 0,
                    Some(x) => x.len(),
                };
                let mut c = vec![vec![usize::MAX; cols]; rows];
                let mut opt = vec![vec![0; cols]; rows];
                for l in 0..rows {
                    for r in (0..cols).rev() {
                        let left_ind = if l == 0 { 0 } else { opt[l - 1][r] };
                        let right_ind = if r + 1 == cols {
                            b.len() - 1
                        } else {
                            opt[l][r + 1]
                        };
                        let (res, ind) = (left_ind..=right_ind)
                            .map(|ind| (a[l][ind] + b[ind][r], ind))
                            .min()
                            .unwrap();
                        c[l][r] = res;
                        opt[l][r] = ind;
                    }
                }
                Core(c)
            }
        }
        mod steady_ant {
            use self::Color::{Blue, Red};
            use super::StickyPermutation;
            use std::iter::FromIterator;
            use std::ops::Index;
            #[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
            enum Color {
                Red,
                Blue,
            }
            #[derive(Debug, Default, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
            struct ColoredPermutation {
                perm: Vec<(Color, usize)>,
            }
            impl Index<usize> for ColoredPermutation {
                type Output = (Color, usize);
                fn index(&self, index: usize) -> &Self::Output {
                    &self.perm[index]
                }
            }
            impl FromIterator<(Color, usize)> for ColoredPermutation {
                fn from_iter<T: IntoIterator<Item = (Color, usize)>>(iter: T) -> Self {
                    let ans = Self {
                        perm: Vec::from_iter(iter),
                    };
                    debug_assert!(ans.is_valid());
                    ans
                }
            }
            impl ColoredPermutation {
                pub fn len(&self) -> usize {
                    self.perm.len()
                }
                pub fn recip(&self) -> Self {
                    let mut perm = vec![(Red, usize::MAX); self.len()];
                    for i in 0..self.len() {
                        perm[self.perm[i].1] = (self.perm[i].0, i);
                    }
                    Self { perm }
                }
                fn is_valid(&self) -> bool {
                    StickyPermutation {
                        perm: self.perm.iter().map(|(_, ind)| *ind).collect(),
                    }
                    .is_valid()
                }
            }
            fn split(recip: &StickyPermutation) -> (StickyPermutation, StickyPermutation) {
                debug_assert!(recip.len() >= 2);
                let mut le = vec![usize::MAX; recip.len() / 2];
                let mut ri = vec![usize::MAX; recip.len() - le.len()];
                let mut index_le = 0usize..;
                let mut index_ri = 0usize..;
                for &value in &recip.perm {
                    if value < le.len() {
                        le[value] = index_le.next().unwrap();
                    } else {
                        ri[value - le.len()] = index_ri.next().unwrap();
                    }
                }
                (
                    StickyPermutation { perm: le },
                    StickyPermutation { perm: ri },
                )
            }
            fn color_cols(perm: &StickyPermutation) -> (Vec<usize>, Vec<usize>) {
                let mut colors = vec![Blue; perm.len()];
                for &i in &perm.perm[0..perm.len() / 2] {
                    colors[i] = Red;
                }
                let mut red = Vec::with_capacity(perm.len() / 2);
                let mut blue = Vec::with_capacity(perm.len() - red.len());
                for (i, color) in colors.into_iter().enumerate() {
                    match color {
                        Red => red.push(i),
                        Blue => blue.push(i),
                    }
                }
                (red, blue)
            }
            pub fn steady_ant(a: &StickyPermutation, b: &StickyPermutation) -> StickyPermutation {
                assert_eq!(a.len(), b.len());
                if a.len() < 2 {
                    return a.clone();
                }
                let br = b.recip();
                let (red_cols, blue_cols) = color_cols(b);
                let (ar_red, ar_blue) = split(&a);
                let (b_red, b_blue) = split(&br);
                let red = &ar_red.recip() + &b_red;
                let blue = &ar_blue.recip() + &b_blue;
                let mut ired = red.perm.iter();
                let mut iblue = blue.perm.iter();
                let c: ColoredPermutation = a
                    .perm
                    .iter()
                    .map(|&middle_index| {
                        if middle_index < red.len() {
                            (Red, red_cols[*ired.next().unwrap()])
                        } else {
                            (Blue, blue_cols[*iblue.next().unwrap()])
                        }
                    })
                    .collect();
                let cr = c.recip();
                let mut perm = vec![usize::MAX; c.len()];
                let mut col: usize = 0;
                for row in (0..perm.len()).rev() {
                    let (hcolor, hcol) = c[row];
                    if hcol == col {
                        col += 1;
                        continue;
                    }
                    if (hcolor == Blue) == (hcol < col) {
                        while col < c.len() {
                            let (vcolor, vrow) = cr[col];
                            if vrow == row {
                                col += 1;
                                break;
                            }
                            if (vcolor == Blue) == (vrow < row) {
                                perm[row] = col;
                                col += 1;
                                break;
                            }
                            col += 1;
                        }
                    }
                }
                for (ind, (_color, value)) in c.perm.iter().enumerate() {
                    if perm[ind] == usize::MAX {
                        perm[ind] = *value;
                    }
                }
                StickyPermutation { perm }
            }
        }
        #[derive(Default, Debug, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
        pub struct StickyPermutation {
            perm: Vec<usize>,
        }
        impl Index<usize> for StickyPermutation {
            type Output = usize;
            fn index(&self, index: usize) -> &Self::Output {
                &self.perm[index]
            }
        }
        impl FromIterator<usize> for StickyPermutation {
            fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> Self {
                let ans = Self {
                    perm: Vec::from_iter(iter),
                };
                debug_assert!(ans.is_valid());
                ans
            }
        }
        impl StickyPermutation {
            pub fn id(n: usize) -> Self {
                Self {
                    perm: (0..n).collect(),
                }
            }
            pub fn len(&self) -> usize {
                self.perm.len()
            }
            pub fn recip(&self) -> Self {
                let mut perm = vec![0; self.len()];
                for i in 0..self.len() {
                    perm[self[i]] = i;
                }
                Self { perm }
            }
            fn is_valid(&self) -> bool {
                let mut tmp = self.perm.clone();
                tmp.sort();
                if let Some(&x) = tmp.first() {
                    if x != 0 {
                        return false;
                    }
                }
                for i in (0..tmp.len()).skip(1) {
                    if tmp[i - 1] + 1 != tmp[i] {
                        return false;
                    }
                }
                true
            }
        }
        impl<'a> Add<&StickyPermutation> for &'a StickyPermutation {
            type Output = StickyPermutation;
            fn add(self, rhs: &StickyPermutation) -> Self::Output {
                debug_assert_eq!(
                    Self::Output::from(&knuth_tropical_multiplication(
                        &Core::from(self),
                        &Core::from(rhs),
                    )),
                    steady_ant(self, rhs)
                );
                steady_ant(self, rhs)
            }
        }
        #[cfg(test)]
        mod test {
            use crate::sticky::permutation::StickyPermutation;
            use std::cmp::Ordering;
            pub fn next_permutation(perm: &mut [usize]) -> bool {
                let last_ascending = match perm.windows(2).rposition(|w| w[0] < w[1]) {
                    Some(i) => i,
                    None => {
                        perm.reverse();
                        return false;
                    }
                };
                let swap_with = perm[last_ascending + 1..]
                    .binary_search_by(|n| usize::cmp(&perm[last_ascending], n).then(Ordering::Less))
                    .unwrap_err();
                perm.swap(last_ascending, last_ascending + swap_with);
                perm[last_ascending + 1..].reverse();
                true
            }
            #[test]
            fn add() {
                for n in 1..7 {
                    let mut a: Vec<_> = (0..n).collect();
                    let mut b = a.clone();
                    loop {
                        loop {
                            let _ = &StickyPermutation { perm: a.clone() }
                                + &StickyPermutation { perm: b.clone() };
                            if !next_permutation(&mut b) {
                                break;
                            }
                        }
                        if !next_permutation(&mut a) {
                            break;
                        }
                    }
                }
            }
        }
    }
    #[derive(Default, Debug, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
    pub struct InfiniteStickyPermutation {
        perm: Vec<i128>,
    }
    impl InfiniteStickyPermutation {
        pub fn id(n: usize) -> Self {
            Self {
                perm: (0..n).map(|x| x as i128).collect(),
            }
        }
        fn is_valid(&self) -> bool {
            let mut tmp = self.perm.clone();
            tmp.sort();
            for i in (0..tmp.len()).skip(1) {
                if tmp[i - 1] == tmp[i] {
                    return false;
                }
            }
            true
        }
        pub fn len(&self) -> usize {
            self.perm.len()
        }
        pub fn lcs(&self, repetitions: i128) -> i128 {
            (0..self.len())
                .map(|index| repetitions.min(self.period_at(index)))
                .sum::<i128>()
        }
        pub fn period(&self, value: i128) -> i128 {
            (self.len() as i128 - 1 - value).div_euclid(self.len() as i128)
        }
        pub fn period_at(&self, index: usize) -> i128 {
            self.period(self.perm[index])
        }
        pub fn recip(&self) -> InfiniteStickyPermutation {
            let mut perm = vec![Default::default(); self.len()];
            for i in 0..self.len() {
                let p = self.period_at(i);
                let shift = p * (self.len() as i128);
                perm[(self.perm[i] + shift) as usize] = i as i128 + shift;
            }
            InfiniteStickyPermutation { perm }
        }
        pub fn repeat(&self, times: i128) -> Self {
            Self {
                perm: (0..times)
                    .flat_map(|k| self.perm.iter().map(move |x| x + k * self.len() as i128))
                    .collect(),
            }
        }
        pub fn ends(&self) -> Vec<i128> {
            let mut ans = self.perm.clone();
            ans.sort();
            ans
        }
    }
    impl Index<usize> for InfiniteStickyPermutation {
        type Output = i128;
        fn index(&self, index: usize) -> &Self::Output {
            &self.perm[index]
        }
    }
    pub fn solve_one_infty<'a, T: PartialEq + 'a>(
        a: impl IntoIterator<Item = &'a T>,
        b: &[T],
    ) -> InfiniteStickyPermutation {
        let mut perm: Vec<_> = (0..b.len() as i128).collect();
        for ch in a.into_iter() {
            if let Some((mut pos, _val)) = b.iter().enumerate().find(|(_ind, val)| ch.eq(val)) {
                let mut horizontal = perm[pos];
                for _i in 0..b.len() {
                    pos += 1;
                    if pos == b.len() {
                        pos = 0;
                        horizontal -= b.len() as i128;
                    }
                    if b[pos] == *ch || horizontal > perm[pos] {
                        swap(&mut horizontal, &mut perm[pos]);
                    }
                }
            }
        }
        InfiniteStickyPermutation { perm }
    }
    impl From<&InfiniteStickyPermutation> for StickyPermutation {
        fn from(value: &InfiniteStickyPermutation) -> Self {
            let mut srt: Vec<_> = value.perm.iter().enumerate().collect();
            srt.sort_by_key(|x| x.1);
            srt.iter()
                .map(|(ind, _)| ind)
                .copied()
                .collect::<Self>()
                .recip()
        }
    }
    impl Mul<u128> for &InfiniteStickyPermutation {
        type Output = InfiniteStickyPermutation;
        fn mul(self, rhs: u128) -> Self::Output {
            match rhs {
                0 => InfiniteStickyPermutation::id(self.len()),
                1 => self.clone(),
                2 => self + self,
                y => {
                    if y % 2 == 0 {
                        &(self * (y / 2)) * 2
                    } else {
                        &(self * (y - 1)) + self
                    }
                }
            }
        }
    }
    impl<'a> Add<&InfiniteStickyPermutation> for &'a InfiniteStickyPermutation {
        type Output = InfiniteStickyPermutation;
        fn add(self, rhs: &InfiniteStickyPermutation) -> Self::Output {
            assert_eq!(self.len(), rhs.len());
            let up = self.repeat(3);
            let down = rhs.repeat(3);
            let rdown = down.recip();
            let starts = up.ends();
            let ends = rdown.ends();
            let a = StickyPermutation::from(&up);
            let rb = StickyPermutation::from(&rdown);
            let b = rb.recip();
            let c = &b + &a;
            let mut ans = vec![i128::MAX; self.len()];
            let mut used = vec![false; ans.len()];
            for i in self.len()..2 * self.len() {
                let from = starts[c[rb[i]]];
                let to = ends[rb[i]];
                let ind = to.rem_euclid(ans.len() as i128);
                let shift = to - ind;
                ans[ind as usize] = from - shift;
                debug_assert!(!replace(
                    &mut used[ans[ind as usize].rem_euclid(ans.len() as i128) as usize],
                    true
                ));
            }
            assert!(!ans.contains(&i128::MAX));
            let ans = Self::Output { perm: ans };
            debug_assert!(ans.is_valid());
            ans
        }
    }
}
fn solve_test(scan: &mut impl Scanner) {
    let l = scan.next();
    let k = scan.next();
    let a: Vec<_> = scan.next::<String>().chars().collect();
    let b: Vec<_> = scan.next::<String>().chars().collect();
    if a.is_empty() || b.is_empty() {
        println!("0");
        return;
    }
    let perm = solve_one_infty(&a, &b);
    println!("{}", (&perm * l).lcs(k));
}
pub fn solve(scan: &mut impl Scanner) {
    let t = 1;
    for _test in 0..t {
        solve_test(scan);
    }
}
#[allow(dead_code)]
fn main() {
    solve(&mut IOScanner::new(std::io::stdin().lock()));
}
pub mod template {
    use std::io::BufRead;
    pub trait Scanner {
        fn next<T: std::str::FromStr>(&mut self) -> T;
        fn seek(&mut self) -> bool;
    }
    pub struct IOScanner<ReadType: BufRead> {
        read: ReadType,
        buffer: Vec<String>,
    }
    impl<ReadType: BufRead> Scanner for IOScanner<ReadType> {
        fn next<T: std::str::FromStr>(&mut self) -> T {
            loop {
                if let Some(token) = self.buffer.pop() {
                    return token.parse().ok().expect("Failed parse");
                }
                let mut input = String::new();
                self.read.read_line(&mut input).expect("Failed read");
                self.buffer = input.split_whitespace().rev().map(String::from).collect();
            }
        }
        fn seek(&mut self) -> bool {
            let mut input = String::new();
            while let Ok(cnt) = self.read.read_line(&mut input) {
                if cnt == 0 {
                    break;
                }
                let line = input.trim();
                if !line.is_empty() && line.matches("=").count() == line.len() {
                    return true;
                }
                input.clear();
            }
            return false;
        }
    }
    impl<ReadType: BufRead> IOScanner<ReadType> {
        pub fn new(read: ReadType) -> IOScanner<ReadType> {
            IOScanner {
                read,
                buffer: Vec::<String>::default(),
            }
        }
    }
}
 

No Comment