#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, flag = 1;
  char c = getchar();
  while ((c > '9' || c < '0') && c != '-') c = getchar();
  if (c == '-') flag = 0, c = getchar();
  while (c <= '9' && c >= '0') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return flag ? x : -x;
}
int get(string s) {
  int ret = 0;
  for (int i = (0); i <= (int)(s.size() - 1); i++) {
    if (s[i] == '1') ret |= (1 << i);
  }
  return ret;
}
const int maxn = 2e6 + 6;
int n, m, k, a[maxn], b[maxn], p[30];
string ss, tt, s[maxn], t[maxn];
int L[maxn], R[maxn];
int main() {
  n = read(), m = read(), k = read();
  cin >> ss >> tt;
  s[0] = ss;
  t[0] = tt;
  for (int i = (1); i <= (int)(n); i++) a[i] = read() - 1, b[i] = read() - 1;
  for (int i = (0); i <= (int)(k); i++) p[i] = i;
  for (int i = 0; i < (1 << k); i++) L[i] = 1e9, R[i] = -1e9;
  for (int i = (1); i <= (int)(n); i++) {
    s[i] = t[i] = string(k, '0');
    swap(p[a[i]], p[b[i]]);
    for (int j = 0; j < k; j++) {
      s[i][p[j]] = ss[j];
      t[i][p[j]] = tt[j];
    }
  }
  for (int i = (0); i <= (int)(n); i++) {
    L[get(s[i])] = min(L[get(s[i])], i);
    R[get(t[i])] = max(R[get(t[i])], i);
  }
  for (int i = (1 << k) - 1; i >= 0; i--) {
    for (int j = 0; j < k; j++)
      if ((1 << j) & i) {
        L[i ^ (1 << j)] = min(L[i ^ (1 << j)], L[i]);
        R[i ^ (1 << j)] = max(R[i ^ (1 << j)], R[i]);
      }
  }
  int ans = 0, l = 1, r = 1;
  for (int i = 0; i < (1 << k); i++) {
    if (R[i] - L[i] >= m) {
      if (__builtin_popcount(i) > ans) {
        ans = __builtin_popcount(i);
        l = L[i] + 1;
        r = R[i];
      }
    }
  }
  printf("%d \n%d %d",
         k + 2 * ans - count(ss.begin(), ss.end(), '1') -
             count(tt.begin(), tt.end(), '1'),
         l, r);
  return 0;
}
