Digital collectible card games have become very popular recently. So Vova decided to try one of these.

Vova has n cards in his collection. Each of these cards is characterised by its power pi, magic number ci and level li. Vova wants to build a deck with total power not less than k, but magic numbers may not allow him to do so — Vova can't place two cards in a deck if the sum of the magic numbers written on these cards is a prime number. Also Vova cannot use a card if its level is greater than the level of Vova's character.

At the moment Vova's character's level is 1. Help Vova to determine the minimum level he needs to reach in order to build a deck with the required total power.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100000).

Then n lines follow, each of these lines contains three numbers that represent the corresponding card: pi, ci and li (1 ≤ pi ≤ 1000, 1 ≤ ci ≤ 100000, 1 ≤ li ≤ n).

Output

If Vova won't be able to build a deck with required power, print  - 1. Otherwise print the minimum level Vova has to reach in order to build a deck.

Examples

Input

5 8
5 5 1
1 5 4
4 6 3
1 12 4
3 12 1


Output

4


Input

3 7
4 4 1
5 8 2
5 3 3


Output

2
#include <bits/stdc++.h>
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long qmul(long long a, long long b, long long m) {
  long long res = 0;
  while (b) {
    if (b & 1) res = (res + a) % m;
    a = (a << 1) % m;
    b = b >> 1;
  }
  return res;
}
inline long long qpow(long long a, long long b, long long m) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b = b >> 1;
  }
  return res;
}
inline long long inv(long long x, long long q) { return qpow(x, q - 2, q); }
using namespace std;
const int N = 300;
const int M = 1e4 + 10;
int dis[N];
struct edge {
  int np, f, ne;
};
edge ed[M];
int head[N];
int si;
void add(int u, int v, int f) {
  ed[si] = edge{v, f, head[u]};
  head[u] = si;
  si++;
}
bool bfs(int s, int tar) {
  memset(dis, 0, sizeof dis);
  queue<int> q;
  q.push(s);
  dis[s] = 1;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = head[cur]; i; i = ed[i].ne) {
      int np = ed[i].np;
      if (!dis[np] && ed[i].f) {
        dis[np] = dis[cur] + 1;
        q.push(np);
      }
    }
  }
  return dis[tar];
}
int dfs(int p, int flo, int tar) {
  if (p == tar) return flo;
  int delta = flo;
  for (int i = head[p]; i; i = ed[i].ne) {
    int np = ed[i].np;
    if (dis[p] + 1 == dis[np] && (ed[i].f)) {
      int d = dfs(np, min(delta, ed[i].f), tar);
      ed[i].f -= d;
      ed[i ^ 1].f += d;
      delta -= d;
    }
    if (delta == 0) break;
  }
  return flo - delta;
}
int dini(int n) {
  int ans = 0;
  while (bfs(1, n)) {
    ans += dfs(1, 0x3f3f3f3, n);
  }
  return ans;
}
bool ex[N];
struct node {
  int p, c, l;
};
bool cmp(const node& a, const node& b) { return a.l < b.l; }
node arr[N];
bool is_not_prime[500000];
long long build(int n, int num) {
  long long tot = 0;
  si = 2;
  memset(head, 0, sizeof head);
  bool exo = false;
  int onep = 0;
  int cnt = 2;
  for (int i = 1; i <= n; i++) {
    if (arr[i].c % 2) {
      if (arr[i].c == 1) {
        onep = max(onep, arr[i].p);
        exo = true;
        continue;
      } else {
        tot += arr[i].p;
        add(1, cnt, arr[i].p);
        add(cnt, 1, 0);
      }
    } else {
      tot += arr[i].p;
      add(cnt, num + 2, arr[i].p);
      add(num + 2, cnt, 0);
    }
    cnt++;
  }
  add(1, cnt, onep);
  add(cnt, 1, 0);
  tot += onep;
  int p1 = 2;
  for (int i = 1; i <= n; i++) {
    if (arr[i].c == 1) continue;
    int p2 = 2;
    for (int j = 1; j <= n; j++) {
      if (arr[j].c == 1) continue;
      if (j > i) {
        if (!is_not_prime[arr[i].c + arr[j].c]) {
          int tp1 = p1, tp2 = p2;
          if (arr[j].c % 2) swap(tp1, tp2);
          add(tp1, tp2, 0x3f3f3f3);
          add(tp2, tp1, 0);
        }
      }
      p2++;
    }
    p1++;
  }
  if (exo) {
    int p = 2;
    for (int i = 1; i <= n; i++) {
      if (arr[i].c == 1) continue;
      if (!is_not_prime[arr[i].c + 1]) {
        add(cnt, p, 0x3f3f3f3);
        add(p, cnt, 0);
      }
      p++;
    }
  }
  return tot;
}
void init() {
  for (int i = 2; i < 500000; i++) {
    if (is_not_prime[i]) continue;
    for (int j = 2 * i; j < 500000; j += i) {
      is_not_prime[j] = true;
    }
  }
}
int main() {
  std::ios::sync_with_stdio(0);
  init();
  int n, k;
  cin >> n >> k;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    int p, l, c;
    cin >> p >> c >> l;
    arr[i] = node{p, c, l};
  }
  sort(arr + 1, arr + n + 1, cmp);
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    int tot = build(mid, n);
    if (tot - dini(n + 2) >= k)
      r = mid - 1;
    else
      l = mid + 1;
  }
  if (l > n)
    cout << -1 << endl;
  else
    cout << arr[l].l << endl;
}
