#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const long long mod = 1e9 + 7;
template <typename T>
inline T gcd(T a, T b) {
  return !b ? a : gcd(b, a % b);
}
template <typename T>
inline T q_pow(T a, T x) {
  T ans = 1, tmp = a;
  while (x) {
    if (x & 1) (ans *= tmp) %= mod;
    (tmp *= tmp) %= mod;
    x >>= 1;
  }
  return ans;
}
template <typename T>
inline void re(T &N) {
  int f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  N = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') N = N * 10 + c - '0';
  N *= f;
}
int m, n, t = 1, st, en, k;
inline int getmask(string &s) {
  int ans = 0;
  for (int i = 0; i < s.size(); i++)
    if (s[i] - '0') ans |= 1 << i;
  return ans;
}
string a, b;
int p[110];
int d[2][1 << 20];
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> m >> k;
  cin >> a >> b;
  for (int i = 0; i < k; i++) p[i] = i;
  for (int i = 0; i < 1 << k; i++) {
    d[0][i] = 1e9;
    d[1][i] = -1e9;
  }
  d[0][getmask(a)] = d[1][getmask(b)] = 0;
  for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;
    swap(p[x - 1], p[y - 1]);
    string _a(k, '0'), _b(k, '0');
    for (int j = 0; j < k; j++) {
      _a[p[j]] = a[j];
      _b[p[j]] = b[j];
    }
    d[0][getmask(_a)] = min(d[0][getmask(_a)], i);
    d[1][getmask(_b)] = max(d[1][getmask(_b)], i);
  }
  pair<int, pair<int, int> > ans = {0, {1, m}};
  int ca = count(a.begin(), a.end(), '1'), cb = count(b.begin(), b.end(), '1');
  for (int i = (1 << k) - 1; ~i; i--) {
    if (d[1][i] - d[0][i] >= m)
      ans = max(ans, {k - ca - cb + 2 * __builtin_popcount(i),
                      {d[0][i] + 1, d[1][i]}});
    for (int j = 0; j < k; j++)
      if (i & (1 << j)) {
        d[0][i ^ (1 << j)] = min(d[0][i ^ (1 << j)], d[0][i]);
        d[1][i ^ (1 << j)] = max(d[1][i ^ (1 << j)], d[1][i]);
      }
  }
  cout << ans.first << '\n'
       << ans.second.first << ' ' << ans.second.second << endl;
  return 0;
}
