#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 500010;

int n, m;
struct Node {
    int x, y, z, p, id, sign; // p为功率，id表示询问ID，sign表示当前这个二位前缀和的符号
    LL sum;
} q[N], tmp[N];
LL ans[N];
int tot;

void solve(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    solve(l, mid), solve(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    LL s = 0;
    while (i <= mid && j <= r) {
        if (q[i].y <= q[j].y) {
            s += q[i].p;
            tmp[k++] = q[i++];
        } else {
            q[j].sum += s;
            tmp[k++] = q[j++];
        }
    }
    while (i <= mid) {
        s += q[i].p;
        tmp[k++] = q[i++];
    }
    while (j <= r) {
        q[j].sum += s;
        tmp[k++] = q[j++];
    }
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, y, p;
        scanf("%d%d%d", &x, &y, &p);
        q[i] = {x, y, 0, p};
    }
    tot = n;
    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        q[tot++] = {x1 - 1, y1 - 1, 1, 0, i, 1};
        q[tot++] = {x2, y2, 1, 0, i, 1};
        q[tot++] = {x1 - 1, y2, 1, 0, i, -1};
        q[tot++] = {x2, y1 - 1, 1, 0, i, -1};
    }
    sort(q, q + tot, [](const Node &a, const Node &b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.y != b.y) return a.y < b.y;
        return a.z < b.z;
    });
    solve(0, tot - 1);
    for (int i = 0; i < tot; i++) {
        if (q[i].z) { // 是询问
            ans[q[i].id] += q[i].sign * q[i].sum;
        }
    }
    for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 100010, M = N << 1;

int n, k;
struct Node {
    int a, b, c, f, cnt;
    bool operator == (const Node &W) const {
        return a == W.a && b == W.b && c == W.c;
    }
} node[N], p[N], tmp[N];
int tot;
int ans[N];
int c[M];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int y) {
    for (int i = x; i <= k; i += lowbit(i)) c[i] += y;
}

inline int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}

void solve(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    solve(l, mid), solve(mid + 1, r);
    // 归并排序+树状数组统计答案，对于每一个j找到所有i，满足a[i]<=a[j]且b[i]<=b[j]，将这些节点i的c值插入树状数组
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (p[i].b <= p[j].b) {
            add(p[i].c, p[i].cnt);
            tmp[k++] = p[i++];
        } else {
            p[j].f += sum(p[j].c);
            tmp[k++] = p[j++];
        }
    }
    while (i <= mid) {
        add(p[i].c, p[i].cnt);
        tmp[k++] = p[i++];
    }
    while (j <= r) {
        p[j].f += sum(p[j].c);
        tmp[k++] = p[j++];
    }
    // 清空树状数组
    for (int t = l; t < i; t++) add(p[t].c, -p[t].cnt);
    // 归并结束时把对于第二维b有序的tmp复制到p中
    for (int i = l, j = 0; i <= r; i++, j++) p[i] = tmp[j];
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        node[i] = {a, b, c};
    }
    // 按照第一维a从小到大排序
    sort(node, node + n, [](const Node &x, const Node &y) {
        if (x.a != y.a) return x.a < y.a;
        else if (x.b != y.b) return x.b < y.b;
        return x.c < y.c;
    });
    // 去重后得到新的p结构体
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j + 1 < n && node[j + 1] == node[j]) j++;
        p[tot++] = {node[i].a, node[i].b, node[i].c, 0, j - i + 1};
        i = j;
    }
    // CDQ分治
    solve(0, tot - 1);
    // 统计答案
    for (int i = 0; i < tot; i++) ans[p[i].f + p[i].cnt - 1] += p[i].cnt;
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, q;
int h[N], e[N], ne[N], idx;
int dfn[N], ts, top[N], sz[N], fa[N], dep[N], son[N], rk[N];
struct Tree {
    int l, r, flag, sum; // flag为-1表示没有标记，0表示该子树全部为0，1表示全部为1
} tr[N << 2];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int depth) {
    dep[u] = depth, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs1(j, depth + 1);
        sz[u] += sz[j];
        if (sz[j] > sz[son[u]]) son[u] = j;
    }
}

void dfs2(int u, int t) {
    dfn[u] = ++ts, rk[ts] = u, top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t); 
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    } 
}

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.flag != -1) {
        left.flag = root.flag, left.sum = root.flag * (left.r - left.l + 1);
        right.flag = root.flag, right.sum = root.flag * (right.r - right.l + 1);
        root.flag = -1;
    }
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, -1, 0};
    } else {
        tr[u] = {l, r, -1};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

// 区间[l,r]置为k
void update(int u, int l, int r, int k) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].flag = k;
        tr[u].sum = k * (tr[u].r - tr[u].l + 1);
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= mid) update(u << 1, l, r, k);
    if (r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}

// 将u到v的路径上所有点的值置为k
void update_path(int u, int v, int k) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, dfn[top[u]], dfn[u], k);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, dfn[v], dfn[u], k);
}

void update_tree(int u, int k) {
    update(1, dfn[u], dfn[u] + sz[u] - 1, k);
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int x; scanf("%d", &x); x++;
        add(x, i); fa[i] = x;
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    // 1表示已安装，0表示未安装 
    for (scanf("%d", &q); q--; ) {
        char op[12]; int x;
        scanf("%s%d", op, &x); x++;
        if (*op == 'i') { // install
            // 将根节点到x全部置为1
            int s = tr[1].sum;
            update_path(1, x, 1);
            printf("%d\n", tr[1].sum - s);
        } else {
            // 将子树x全部置0
            int s = tr[1].sum;
            update_tree(x, 0);
            printf("%d\n", s - tr[1].sum);
        } 
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, M = N << 1;

int n, m;
int a[N], na[N]; // na表示新编号
int h[N], e[M], ne[M], idx;
struct Tree {
    int l, r;
    LL sum, add;
} tr[N << 2];
int dfn[N], ts; // dfn表示dfs序（优先遍历重儿子）
int dep[N], sz[N], top[N], fa[N], son[N];
// dep[i]表示i的深度（根节点的深度为1）,sz[i]表示以i为根的子树的大小
// top[i]表示i所在重链的顶点，fa[i]表示i的父结点，son[i]表示子树i的重儿子

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int father, int depth) {
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

// 点u所属的重链的顶点为t
void dfs2(int u, int t) {
    dfn[u] = ++ts, na[ts] = a[u], top[u] = t;
    if (!son[u]) return; // u为叶结点
    dfs2(son[u], t); // 重儿子
    // 处理轻儿子
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j); // 轻儿子所处重链的顶点就是自己 
    }
}

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, na[r], 0};
    } else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void pushdown(int u) {
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
        left.add += root.add, left.sum += root.add * (left.r - left.l + 1);
        right.add += root.add, right.sum += root.add * (right.r - right.l + 1);
        root.add = 0;
    }
}

// 将[l,r]区间加上k
void update(int u, int l, int r, int k) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].add += k;
        tr[u].sum += k * (tr[u].r - tr[u].l + 1);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, k);
    if (r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}

// 求[l,r]区间和
LL query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].sum;
    }
    pushdown(u); // 下传add标记
    LL res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

// 将树上u->v的路径全部加上k
void update_path(int u, int v, int k) {
    while (top[u] != top[v]) { // u,v不在同一个重链上
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        // 加上u所在的重链和和
        // 其区间为[dfn[top[u]], dfn[u]]
        update(1, dfn[top[u]], dfn[u], k);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    // 加上u-v之间路径的和
    update(1, dfn[v], dfn[u], k);
}

// 求树上u-v之间的路径和
LL query_path(int u, int v) {
    LL res = 0;
    while (top[u] != top[v]) { // u,v不在同一个重链上
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        // 加上u所在的重链和和
        // 其区间为[dfn[top[u]], dfn[u]]
        res += query(1, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    // 加上u-v之间路径的和
    res += query(1, dfn[v], dfn[u]);
    return res;
}

// 将树上以u为根的子树全部加上k
void update_tree(int u, int k) {
    // 对应区间 [dfn[u], dfn[u]+sz[u]-1]
    update(1, dfn[u], dfn[u] + sz[u] - 1, k);
}

// 求树上以u为根的子树的和
LL query_tree(int u) {
    // 对应区间 [dfn[u], dfn[u]+sz[u]-1]
    return query(1, dfn[u], dfn[u] + sz[u] - 1);
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs1(1, -1, 1); // 预处理dep,fa,sz
    dfs2(1, 1); // 求dfs序dfn,top
    build(1, 1, n); // 建立线段树
    for (scanf("%d", &m); m--; ) {
        int type, u, v, k;
        scanf("%d", &type);
        if (type == 1) {
            scanf("%d%d%d", &u, &v, &k);
            update_path(u, v, k);
        } else if (type == 2) {
            scanf("%d%d", &u, &k);
            update_tree(u, k);
        } else if (type == 3) {
            scanf("%d%d", &u, &v);
            printf("%lld\n", query_path(u, v));
        } else {
            scanf("%d", &u);
            printf("%lld\n", query_tree(u));
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 810, INF = 1e8;
const double eps = 1e-8;

int n, m, S, T;
int h[N], e[M], ne[M], bw[M], idx;
double w[M];
int q[N], d[N], cur[N];

void add(int a, int b, int c) {
    e[idx] = b, bw[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, bw[idx] = c, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() {
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && w[i] > 0) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                q[++tt] = j;
                if (j == T) return true;
            }
        }
    }
    return false;
}

double find(int u, double limit) {
    if (u == T) return limit;
    double flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        cur[u] = i;
        if (d[j] == d[u] + 1 && w[i] > 0) {
            double t = find(j, min(w[i], limit - flow));
            if (t < eps) d[j] = -1;
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

double dinic() {
    double max_flow = 0;
    while (bfs()) while (double flow = find(S, INF)) max_flow += flow; 
    return max_flow;
}

bool check(double mid) {
    double tot = 0;
    for (int i = 0; i < idx; i += 2) {
        double x = bw[i] - mid;
        if (x < 0) tot += x, w[i] = w[i ^ 1] = 0;
        else w[i] = w[i ^ 1] = x;
    }
    return tot + dinic() < 0;
}


int main() {
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    double l = 0, r = 1e7;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%.2f\n", l);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 200010, INF = 1e9;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int q[N];
int d[N], cur[N]; // d[i]表示点i的层次，cur[i]表示i的当前弧

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() { // 判断残留网络是否存在增广路（即从S到T存在边全大于0的路径）
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && w[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                q[++tt] = j;
                if (j == T) return true; // 找到了增广路，此时增广路的流量即f[T]
            }
        }
    }
    return false; // 残留网络不存在增广路，那么此时原图的可行流流量就是最大流
}

// 从起点到u，流量最大值为limit
int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0; // u->T的流量
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        cur[u] = i; // 更新当前弧
        if (d[j] == d[u] + 1 && w[i]) {
            int t = find(j, min(w[i], limit - flow));
            if (!t) d[j] = -1; // 删点
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) while (int flow = find(S, INF)) max_flow += flow;
    return max_flow;
}

int main() {
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c; 
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); // 初始流量为0，对于原图的残留网络，正向边容量为c-0=c，反向边容量为0+0=0
    }
    printf("%d\n", dinic());
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = (N * N + 2 * N) * 2, INF = 1e9;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int q[N], d[N], cur[N];
int S, T;
int a[1010], last[1010]; // last[i]表示猪圈i上一次由顾客打开的顾客编号

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() {
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && w[i]) {
                d[j] = d[t] + 1;
                q[++tt] = j;
                cur[j] = h[j];
                if (j == T) return true;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        cur[u] = i;
        if (d[j] == d[u] + 1 && w[i]) {
            int t = find(j, min(w[i], limit - flow));
            if (t == 0) d[j] = -1;
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) while (int flow = find(S, INF)) max_flow += flow;
    return max_flow;
}

int main() {
    scanf("%d%d", &m, &n);
    memset(h, -1, sizeof h);
    S = N - 1, T = N - 2;
    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        int A; scanf("%d", &A);
        for (int j = 0; j < A; j++) {
            int x; scanf("%d", &x);
            if (last[x] == 0) add(S, i, a[x]);
            else add(last[x], i, INF);
            last[x] = i;
        }
        int B; scanf("%d", &B);
        add(i, T, B);
    }
    printf("%d\n", dinic());
    return 0;
}

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 210, M = 30010, INF = 1e9;
const double eps = 1e-8;

int Case, n;
double D;
PII p[N];
int h[N], e[M], w[M], ne[M], idx;
int q[N], d[N], cur[N];
int S, T, tot;
vector<int> res;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool check(int a, int b) {
    double dx = p[a].x - p[b].x, dy = p[a].y - p[b].y;
    return dx * dx + dy * dy < D * D + eps;
}

bool bfs() {
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && w[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                q[++tt] = j;
                if (j == T) return true;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = h[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        if (d[j] == d[u] + 1 && w[i]) {
            int t = find(j, min(w[i], limit - flow));
            if (!t) d[j] = -1;
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) while (int flow = find(S, INF)) max_flow += flow;
    return max_flow;
}

int main() {
    for (cin >> Case; Case--; ) {
        memset(h, -1, sizeof h);
        idx = 0; res.clear();
        S = N - 1, tot = 0;
        scanf("%d%lf", &n, &D);
        for (int i = 0; i < n; i++) {
            int x, y, a, b;
            scanf("%d%d%d%d", &x, &y, &a, &b);
            p[i] = {x, y};
            add(S, i, a);
            add(i, n + i, b);
            tot += a;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (check(i, j)) {
                    add(n + i, j, INF);
                    add(n + j, i, INF);
                }
            }
        }
        // 枚举T
        for (T = 0; T < n; T++) {
            // 还原残留网络
            for (int i = 0; i < idx; i += 2) {
                w[i] += w[i ^ 1], w[i ^ 1] = 0;
            }
            if (dinic() == tot) res.push_back(T);
        }
        if (res.size()) {
            for (auto x : res) printf("%d ", x);
            puts("");
        } else {
            puts("-1");
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = N * N, INF = 1e9;

int n;
int a[N], f[N];
int h[N], e[M], w[M], ne[M], idx;
int q[N], d[N], cur[N];
int S, T;
int res, s;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() {
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && w[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                q[++tt] = j;
                if (j == T) return true;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = h[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        if (d[j] == d[u] + 1 && w[i]) {
            int t = find(j, min(w[i], limit - flow));
            if (!t) d[j] = -1;
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) while (int flow = find(S, INF)) max_flow += flow;
    return max_flow;
}

int main() {
    memset(h, -1, sizeof h);
    S = N - 1, T = N - 2;
    scanf("%d", &n); 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        s = max(s, f[i]);
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i] && f[i] == f[j] + 1) {
                add(n + j, i, 1);
            }
        }
        add(i, i + n, 1);
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] == 1) add(S, i, 1);
        if (f[i] == s) add(n + i, T, 1); 
    }
    if (s == 1) return 0 * printf("%d\n%d\n%d\n", 1, n, n);
    res = dinic();
    printf("%d\n%d\n", s, res);    
    for (int i = 0; i < idx; i += 2) {
        int a = e[i ^ 1], b = e[i];
        if (a == S && b == 1) w[i] = INF;
        else if (a == 1 && b == n + 1) w[i] = INF;
        else if (a == n + n && b == T) w[i] = INF;
        else if (a == n && b == n + n) w[i] = INF;
    }
    printf("%d\n", res + dinic());
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 410, M = (N * N * 2 + N * 3) * 2, INF = 1e9;

int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int q[N], d[N], cur[N];
int S, T;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() {
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && w[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                q[++tt] = j;
                if (j == T) return true;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        cur[u] = i;
        if (d[j] == d[u] + 1 && w[i]) {
            int t = find(j, min(w[i], limit - flow));
            if (!t) d[j] = -1;
            w[i] -= t, w[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) while (int flow = find(S, INF)) max_flow += flow;
    return max_flow;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    memset(h, -1, sizeof h);
    S = N - 1, T = N - 2;
    for (int i = 1; i <= m; i++) add(S, 2 * n + i, 1);
    for (int i = 1; i <= k; i++) add(2 * n + m + i, T, 1);
    for (int i = 1; i <= n; i++) {
        add(i, n + i, 1);
        int a, b;
        scanf("%d%d", &a, &b);
        for (int j = 0; j < a; j++) {
            int x; scanf("%d", &x);
            add(2 * n + x, i, 1);
        }
        for (int j = 0; j < b; j++) {
            int x; scanf("%d", &x);
            add(n + i, 2 * n + m + x, 1);
        }
    }
    printf("%d\n", dinic());
    return 0;
}