#include #define all(x) x.begin(), x.end() #define lb(v, a) (int)(lower_bound(all(v), a) - v.begin()) using namespace std; template using V = vector; bool check(int& N, V& K, V >& A, int& m) { V P = {}; int q_max = 0; for (int i = 0; i < N; ++i) { int s = A[i].size() - lb(A[i], m); if (s < A[i].size()) { P.push_back(s); } else if (q_max < s) { q_max = s; } } sort(all(P)); multiset mst = {}; for (int i = N - 1; i >= P.size(); --i) { mst.insert(K[i]); } if (mst.empty() == false and q_max >= *mst.begin()) { return true; } for (int i = P.size() - 1; i >= 0; --i) { int u = mst.empty() ? K[i] : min(*mst.begin(), K[i]); if (P[i] >= u) { return true; } else if (P[i] < u - 1) { return false; } else if (mst.empty() == false and P[i] == *mst.begin() - 1 and q_max >= K[i]) { return true; } else if (mst.empty()) { continue; } mst.erase(mst.begin()); mst.insert(K[i]); } return true; } int main(void) { int N; cin >> N; V K(N); for (int i = 0; i < N; ++i) { cin >> K[i]; } V T(N); V > A(N, V({})); V st = {}; for (int i = 0; i < N; ++i) { cin >> T[i]; for (int j = 0; j < T[i]; ++j) { int a; cin >> a; A[i].push_back(a); st.push_back(a); } sort(all(A[i])); } st.erase(unique(all(st)), st.end()); sort(all(st)); int ok = 0, ng = st.size(); while (ng - ok > 1) { int t = (ok + ng) >> 1; if (check(N, K, A, st[t])) { ok = t; } else { ng = t; } } int ans = st[ok]; cout << ans << endl; return 0; }