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.

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).

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.

  1 /**  2  * Codeforces  3  * Problem#808F  4  * Accepted  5  * Time:62ms  6  * Memory:10300k  7  */   8 #include <iostream>  9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 #define smin(a, b) a = min(a, b) 33 #define smax(a, b) a = max(a, b) 34 #define max3(a, b, c) max(a, max(b, c)) 35 #define min3(a, b, c) min(a, min(b, c)) 36 template<typename T> 37 inline boolean readInteger(T& u){ 38     char x; 39     int aFlag = 1; 40     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 41     if(x == -1) { 42         ungetc(x, stdin); 43         return false; 44     } 45     if(x == ‘-‘){ 46         x = getchar(); 47         aFlag = -1; 48     } 49     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 50     ungetc(x, stdin); 51     u *= aFlag; 52     return true; 53 } 54  55 ///map template starts 56 typedef class Edge{ 57     public: 58         int end; 59         int next; 60         int flow; 61         int cap; 62         int lvl; 63         Edge(int end = 0, int next = 0, int flow = 0, int cap = 0, int lvl = 0):end(end), next(next), flow(flow), cap(cap), lvl(lvl) {    } 64 }Edge; 65  66 typedef class MapManager{ 67     public: 68         int ce; 69         int *h; 70         Edge *edge; 71         MapManager() {    } 72         MapManager(int points, int limit):ce(0) { 73             h = new int[(const int)(points + 1)]; 74             edge = new Edge[(const int)(limit + 1)]; 75             memset(h, 0, sizeof(int) * (points + 1)); 76         } 77          78         inline void addEdge(int from, int end, int flow, int cap, int lvl) { 79             edge[++ce] = Edge(end, h[from], flow, cap, lvl); 80             h[from] = ce; 81         } 82          83         inline void addDoubleEdge(int from, int end, int cap, int lvl) { 84             addEdge(from, end, 0, cap, lvl); 85             addEdge(end, from, cap, cap, lvl); 86         } 87          88         Edge& operator [] (int pos) { 89             return edge[pos]; 90         } 91          92         inline int reverse(int i) { 93             return (i & 1) ? (i + 1) : (i - 1); 94         } 95          96         inline void clone(MapManager& g, int n) { 97             g.ce = ce; 98             memcpy(g.h, h, sizeof(int) * (n + 1)); 99             memcpy(g.edge, edge, sizeof(Edge) * (ce + 1));100         }101 }MapManager;102 #define m_begin(g, i) (g).h[(i)]103 ///map template ends104 105 int n, m;106 int csum = 0;107 int *ps, *cs, *ls;108 inline void init() {109     readInteger(n);110     readInteger(m);111     ps = new int[(const int)(n + 1)];112     cs = new int[(const int)(n + 1)];113     ls = new int[(const int)(n + 1)];114     for(int i = 1; i <= n; i++) {115         readInteger(cs[i]);116         readInteger(ps[i]);117         readInteger(ls[i]);118         csum += ps[i];119     }120 }121 122 int num = 0;123 int pri[500000];124 boolean* vis;125 inline void Euler() {126     vis = new boolean[(const int)(csum + 1)];127     memset(vis, false, sizeof(boolean) * (csum + 1));128     vis[1] = true;129     for(int i = 2; i <= csum; i++) {130         if(!vis[i]) pri[++num] = i;131         for(int j = 1; j <= num; j++) {132             long long x = pri[j] * 1LL * i;133             if(x > csum)    break;134             vis[x] = true;135             if((i % pri[j]) == 0)    break;136         }137     }138 }139 140 int s, t;141 MapManager g;142 MapManager mg;143 inline void init_map() {144     s = 0, t = 2 * n + 1;145     g = MapManager(2 * n + 1, 4 * n * n);146     mg = MapManager(2 * n + 1, 4 * n * n);147     for(int i = 1; i <= n; i++) {148         mg.addDoubleEdge(s, i, cs[i], ls[i]);149         mg.addDoubleEdge(i + n, t, cs[i], ls[i]);150 //        if(!vis[ps[i]])151 //            mg.addDoubleEdge(i, i + n, cs[i], ls[i]);152         for(int j = i + 1; j <= n; j++) {153             if(!vis[ps[i] + ps[j]]) {154                 mg.addDoubleEdge(i, j + n, inf, 0);155                 mg.addDoubleEdge(j, i + n, inf, 0);156             }157         }158     }159     delete[] vis;160 }161 162 int* dis;163 queue<int> que;164 inline boolean bfs(int mid) {165     memset(vis, false, sizeof(boolean) * (t + 1));166     que.push(s);167     vis[s] = true;168     dis[s] = 0;169     while(!que.empty()) {170         int e = que.front();171         que.pop();172         for(int i = m_begin(g, e); i; i = g[i].next) {173             if(g[i].lvl > mid)    continue;174             if(g[i].cap == g[i].flow)    continue;175             int eu = g[i].end;176             if(vis[eu])    continue;177             vis[eu] = true;178             dis[eu] = dis[e] + 1;179             que.push(eu);180         }181     }182     return vis[t];183 }184 185 int *cur;186 inline int blockedflow(int node, int minf, int& mid) {187     if((node == t) || (minf == 0))    return minf;188     int f, flow = 0;189     for(int& i = cur[node]; i; i = g[i].next) {190         int& eu = g[i].end;191         if(g[i].lvl <= mid && dis[eu] == dis[node] + 1 && g[i].flow < g[i].cap && (f = blockedflow(eu, min(minf, g[i].cap - g[i].flow), mid)) > 0) {192             minf -= f;193             flow += f;194             g[i].flow += f;195             g[g.reverse(i)].flow -= f;196             if(minf == 0)    return flow;197         }198     }199     return flow;200 }201 202 inline void init_dinic() {203     vis = new boolean[(const int)(t + 1)];204     dis = new int[(const int)(t + 1)];205     cur = new int[(const int)(t + 1)];206 }207 208 inline int dinic(int mid) {209     int maxflow = 0;210     int cc = 0;211     mg.clone(g, t);212     for(int i = 1; i <= n; i++)213         if(ls[i] <= mid)214             cc += cs[i];215     if(cc < m)216         return cc;217     while(bfs(mid)) {218         for(int i = 0; i <= t; i++)219             cur[i] = m_begin(g, i);220         maxflow += blockedflow(s, inf, mid);221     }222     return cc - (maxflow >> 1);223 }224 225 inline void solve() {226     int l = 1, r = n;227     while(l <= r) {228         int mid = (l + r) >> 1;229         if(dinic(mid) < m)    l = mid + 1;230         else r = mid - 1;231     }232     if(r == n)    puts("-1");233     else printf("%d", r + 1);234 }235 236 int main() {237     init();238     Euler();239     init_map();240     init_dinic();241     solve();242     return 0;243 }