Recently, the Fair Nut has written k strings of length n, consisting of letters "a" and "b". He calculated c — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.

Then, he lost his sheet with strings. He remembers that all written strings were lexicographically not smaller than string s and not bigger than string t. He is interested: what is the maximum value of c that he could get.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

  * a is a prefix of b, but a ≠ b;
  * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input

The first line contains two integers n and k (1 ≤ n ≤ 5 ⋅ 10^5, 1 ≤ k ≤ 10^9).

The second line contains a string s (|s| = n) — the string consisting of letters "a" and "b.

The third line contains a string t (|t| = n) — the string consisting of letters "a" and "b.

It is guaranteed that string s is lexicographically not bigger than t.

Output

Print one number — maximal value of c.

Examples

Input


2 4
aa
bb


Output


6


Input


3 3
aba
bba


Output


8


Input


4 5
abbb
baaa


Output


8

Note

In the first example, Nut could write strings "aa", "ab", "ba", "bb". These 4 strings are prefixes of at least one of the written strings, as well as "a" and "b". Totally, 6 strings.

In the second example, Nut could write strings "aba", "baa", "bba".

In the third example, there are only two different strings that Nut could write. If both of them are written, c=8.
import java.util.*;
import java.io.*;

// Solution

public class Main 
{    
  public static void main (String[] argv) 
  {
	  new Main();
  } 
     
     
  
  boolean test = false;  
  
  final int MOD = 1000000007;
  
  
  class Edge {
      int p, q, w;
      
      public Edge(int p, int q, int w) {
          this.p = p;
          this.q = q;
          this.w = w;
      }
      
      private int other(int v) {
          return v == p ? q : p;
      }
  }
  
 
  
  public Main()   {
	 FastReader in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
	// FastReader in = new FastReader(new BufferedReader(new FileReader("Main.in")));
     
     
     
     int n = in.nextInt();
     int k = in.nextInt();
     
     char[] lo = in.next().toCharArray();
     char[] hi = in.next().toCharArray();
     
     long tot = 0;
     int  frontier_size = 1;  
     for (int i = 0; i < n; i++) {
         frontier_size *= 2;
         if (lo[i] == 'b') --frontier_size;
         if (hi[i] == 'a') --frontier_size;
         
         if (frontier_size >= k) {
             tot += 1L * k * (n - i);
             break;
         }
         
         tot += frontier_size;
     }
     System.out.println(tot);
  }
  
 
  private int mod_add(int a, int b) {
      int v = a + b;
      if (v >= MOD) v -= MOD;
      return v;
  }
  
  
  private long overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
      if (x1 > x3) return overlap(x3, y3, x4, y4, x1, y1, x2, y2);
      
      if (x3 > x2 || y4 < y1 || y3 > y2) return 0L;
      
      //(x3, ?, x2, ?)
      int yL = Math.max(y1, y3);
      int yH = Math.min(y2, y4);
      int xH = Math.min(x2, x4);
      
      return f(x3, yL, xH, yH);
  }
  //return #black cells in rectangle
  private long f(int x1, int y1, int x2, int y2) {
      long dx = 1L + x2 - x1;
      long dy = 1L + y2 - y1;
      if (dx % 2 == 0 || dy % 2 == 0 || (x1 + y1) % 2 == 0) 
          return 1L * dx * dy / 2;
      return 1L * dx * dy / 2 + 1;
  }
  
  private int dist(int x, int y, int xx, int yy) {
      return abs(x - xx) + abs(y - yy);
  }
  
  private boolean less(int x, int y, int xx, int yy) {
      return x < xx || y > yy;
  }
  
  private int mul(int x, int y) {
      return (int)(1L * x * y % MOD);
  }
  
  private int add(int x, int y) {
      return (x + y) % MOD;
  }
  
 
  
  private int nBit1(int v) {
      int v0 = v;
      int c = 0;
      while (v != 0) {
          ++c;
          v = v & (v - 1);
      }
      return c;
  }
  
  private long abs(long v) {
      return v > 0 ? v : -v;
  }
  
  private int abs(int v) {
      return v > 0 ? v : -v;
  }
  
  private int common(int v) {
      int c = 0;
      while (v != 1) {
          v = (v >>> 1);
          ++c;
      }
      
      return c;
  }
  
  private void reverse(char[] a, int i, int j) {
      while (i < j) {
          swap(a, i++, j--);
      }
  }
  
  private void swap(char[] a, int i, int j) {
      char t = a[i];
      a[i] = a[j];
      a[j] = t;
  }
  
  private int gcd(int x, int y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private long gcd(long x, long y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private int max(int a, int b) {
      return a >  b ? a : b;
  }
  
  private long max(long a, long b) {
      return a >  b ? a : b;
  }
  
  private int min(int a, int b) {
      return a >  b ? b : a;
  }
  
  private long min(long a, long b) {
      return a >  b ? b : a;
  }
  
  static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader(BufferedReader in)
        {            
            br = in;
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    String line = br.readLine();
                    if (line == null || line.length() == 0) return "";
                    st = new StringTokenizer(line);
                }
                catch (IOException  e)
                {
                    return "";
                    //e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                return "";
                //e.printStackTrace();
            }
            return str;
        }
    }
}