#include <bits/stdc++.h>
using namespace std;
const int K = 21, N = 1e6 + 7;
int pa[N], pb[N];
int dp[K][1 << K];
int maxidx[1 << K];
int l[N], r[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  string sa, sb;
  int a = 0, b = 0;
  cin >> sa >> sb;
  for (int i = 0; i < k; i++) a |= (sa[i] - '0') << i;
  for (int i = 0; i < k; i++) b |= (sb[i] - '0') << i;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    l[i] = x;
    r[i] = y;
  }
  vector<int> perm;
  perm.resize(k);
  iota(perm.begin(), perm.end(), 0);
  for (int i = n; i >= 0; i--) {
    int x = l[i], y = r[i];
    int idx, idy;
    for (int j = 0; j < k; j++) {
      if (perm[j] == x) idx = j;
      if (perm[j] == y) idy = j;
    }
    swap(perm[idx], perm[idy]);
    for (int j = 0; j < k; j++) {
      if (a & (1 << perm[j])) pa[i] |= 1 << j;
      if (b & (1 << perm[j])) pb[i] |= 1 << j;
    }
  }
  int a1 = __builtin_popcount(a);
  int b1 = __builtin_popcount(b);
  fill(maxidx, maxidx + (1 << K), -1);
  for (int i = 0; i <= n; i++) maxidx[pb[i]] = i;
  for (int i = 0; i < k; i++)
    for (int mask = 0; mask < (1 << k); mask++)
      if ((mask & (1 << i)) == 0)
        maxidx[mask] = max(maxidx[mask], maxidx[mask ^ (1 << i)]);
  for (int b = 0; b <= k; b++) {
    for (int mask = 0; mask < (1 << k); mask++)
      if (__builtin_popcount(mask) == b)
        dp[b][mask] = maxidx[mask];
      else
        dp[b][mask] = -1;
    for (int i = 0; i < k; i++) {
      for (int mask = 0; mask < (1 << k); mask++)
        if ((mask & (1 << i)))
          dp[b][mask] = max(dp[b][mask], dp[b][mask ^ (1 << i)]);
    }
  }
  int ans = -1, l, r;
  for (int i = 0; i <= n; i++) {
    int x = pa[i];
    int best = 0;
    for (int b = 0; b <= k; b++) {
      if (dp[b][x] >= i + m) best = b;
    }
    int cur = k - a1 - b1 + 2 * best;
    if (cur > ans) {
      ans = cur;
      l = i + 1;
      r = dp[best][x];
    }
  }
  cout << ans << endl;
  cout << l << " " << r << endl;
}
