#include <bits/stdc++.h>
using namespace std;
int popcnt(int x) {
  int ct = 0;
  for (; x > 0; x &= (x - 1)) ct++;
  return ct;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  string bs, bt;
  cin >> bs >> bt;
  int s = 0;
  int t = 0;
  for (int i = 0; i < k; i++) {
    s |= (bs[i] - '0') << i;
    t |= (bt[i] - '0') << i;
  }
  vector<pair<int, int>> swaps;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    swaps.push_back({a, b});
  }
  vector<int> perm;
  for (int i = 0; i < k; i++) {
    perm.push_back(i);
  }
  vector<int> revs_s;
  vector<int> revs_t;
  revs_s.push_back(s);
  revs_t.push_back(t);
  for (int i = 0; i < n; i++) {
    int a, b;
    tie(a, b) = swaps[i];
    vector<int> swap_perm;
    for (int j = 0; j < k; j++) {
      swap_perm.push_back(j);
    }
    swap(swap_perm[a], swap_perm[b]);
    vector<int> new_perm(k);
    for (int j = 0; j < k; j++) {
      new_perm[j] = perm[swap_perm[j]];
    }
    int s1 = 0;
    int t1 = 0;
    for (int j = 0; j < k; j++) {
      s1 |= ((s >> j) & 1) << new_perm[j];
      t1 |= ((t >> j) & 1) << new_perm[j];
    }
    revs_s.push_back(s1);
    revs_t.push_back(t1);
    perm.swap(new_perm);
  }
  vector<int> dp_s(1 << k, n + 1);
  vector<int> dp_t(1 << k, -1);
  for (int i = 0; i <= n; i++) {
    dp_s[revs_s[i]] = min(dp_s[revs_s[i]], i);
    dp_t[revs_t[i]] = max(dp_t[revs_t[i]], i);
  }
  for (int mask = (1 << k) - 1; mask >= 0; mask--) {
    for (int i = 0; i < k; i++) {
      int mask1 = mask & (~(1 << i));
      dp_s[mask1] = min(dp_s[mask1], dp_s[mask]);
      dp_t[mask1] = max(dp_t[mask1], dp_t[mask]);
    }
  }
  int mx = 0;
  int mxl = 0, mxr = n;
  for (int mask = 0; mask < (1 << k); mask++) {
    int cnt = popcnt(mask);
    if (dp_t[mask] - dp_s[mask] >= m && cnt > mx) {
      mxl = dp_s[mask];
      mxr = dp_t[mask];
      mx = cnt;
    }
  }
  cout << (2 * mx + k - popcnt(s) - popcnt(t)) << endl;
  cout << (mxl + 1) << " " << mxr << endl;
  return 0;
}
