# Homework

Taro is a student of Ibaraki College of Prominent Computing. In this semester, he takes two courses, mathematics and informatics. After each class, the teacher may assign homework. Taro may be given multiple assignments in a single class, and each assignment may have a different deadline. Each assignment has a unique ID number.

Everyday after school, Taro completes at most one assignment as follows. First, he decides which course's homework to do at random by ipping a coin. Let S be the set of all the unfinished assignments of the chosen course whose deadline has not yet passed. If S is empty, he plays a video game without doing any homework on that day even if there are unfinished assignments of the other course. Otherwise, with T⊆S being the set of assignments with the nearest deadline among S, he completes the one with the smallest assignment ID among T.

The number of assignments Taro will complete until the end of the semester depends on the result of coin ips. Given the schedule of homework assignments, your task is to compute the maximum and the minimum numbers of assignments Taro will complete.

# Input

The input consists of a single test case in the following format.

n m

s1 t1

...

sn tn

The first line contains two integers n and m satisfying $1 \leq m < n \leq 400$. n denotes the total number of assignments in this semester, and $m$denotes the number of assignments of the mathematics course (so the number of assignments of the informatics course is $n-m$). Each assignment has a unique ID from $1$to $n$; assignments with IDs $1$through m are those of the mathematics course, and the rest are of the informatics course. The next $n$lines show the schedule of assignments. The $i$-th line of them contains two integers $s_i$and $t_i$satisfying $1\leq s_i \leq t_i \leq 400$, which means that the assignment of ID $i$is given to Taro on the $s_i$-th day of the semester, and its deadline is the end of the $t_i$-th day.

# Output

In the first line, print the maximum number of assignments Taro will complete. In the second line, print the minimum number of assignments Taro will complete.

# Sample Input 1

6 3
1 2
1 5
2 3
2 6
4 5
4 6

# Sample Output 1

6
2

# Sample Input 2

6 3
1 1
2 3
4 4
1 1
2 4
3 3

# Sample Output 2

4
3

# Solution

# 思路

开这题的时候已经只剩下15分钟了。。第二问就没有写完。

第一问：

求能完成的最多的作业的时候可以不考虑科目随意完成一门作业。

模拟：所有作业按起点排序按天扫描，把扫描到的作业的ddl扔到一个堆里，每天取一门最近的那个作业做掉，过了ddl的作业弹掉。这样就能做最多的作业

二分图匹配：每天只能写一门作业，将天数与这一天能可以完成的作业连边求最大匹配数。（没有试过 应该ok）

第二问：

求能完成的最少的作业相当于求最多必须做作业的天数。可以观察到如果某一天既有cs的作业又有math的作业那这天就必做作业。那么所有cs作业向其时间内的每一天连边，所有math作业也向其时间内的每一天连边。cs作业连源，math作业连汇，跑最大流即可得出结果。

# Code

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e4;
const int M = 2e5 + 10;
const int Inf = 0x3f3f3f3f;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

struct edge_
{
    int to, next, c;
} edge[M];
int head[N], cnt = 1;
void insert(int u, int v, int c)
{
    edge[++cnt] = (edge_){v, head[u], c};
    head[u] = cnt;
}
void Insert(int u, int v, int c)
{
    insert(u, v, c);
    insert(v, u, 0);
}

int n, m, S, T, s[N], t[N];
void readin()
{
    n = read(); m = read();
    for (int i = 1; i <= n; ++i)
    {
        s[i] = read();
        t[i] = read();
    }
}

queue<int> q;
int dis[N];
bool inq[N];
bool spfa()
{
    for (int i = S; i <= T; ++i)
        dis[i] = -1;
    memset(inq, false, sizeof(inq));
    q.push(S);
    dis[S] = 0;
    inq[S] = true;
    while (!q.empty())
    {
        int now = q.front();
        for (int i = head[now]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (edge[i].c && dis[v] == -1)
            {
                dis[v] = dis[now] + 1;
                if (!inq[v])
                {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
        q.pop();
        inq[now] = false;
    }
    return dis[T] != -1;
}
int dfs(int u, int f)
{
    if (u == T)
        return f;
    int w, used = 0;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (dis[v] == dis[u] + 1)
        {
            w = dfs(v, min(edge[i].c, f - used));
            edge[i].c -= w;
            edge[i ^ 1].c += w;
            used += w;
            if (used == f)
                return f;
        }
    }
    if (!used)
        dis[u] = -1;
    return used;
}

int dinic()
{
    int ans = 0;
    while (spfa())
        ans += dfs(S, Inf);
    return ans;
}

priority_queue<int, vector<int>, greater<int> > pq;
int tag[N];
bool cmp(int a, int b)
{
    return s[a] < s[b];
}
void solve()
{
    int ans1 = 0, ans2 = 0;

    memset(head, 0, sizeof(head));
    cnt = 1;
    
    S = 0; T = 3 * 400 + 1;
    for (int i = 1; i <= m; ++i)
    {
        Insert(S, i, 1);
        for (int j = s[i]; j <= t[i]; ++j)
            Insert(i, j + 400, 1);
    }
    for (int i = 1; i <= 400; ++i)
        Insert(i + 400, i + 800, 1);
    for (int i = m + 1; i <= n; ++i)
    {
        Insert(i, T, 1);
        for (int j = s[i]; j <= t[i]; ++j)
            Insert(j + 800, i, 1);
    }
    ans2 = dinic();


    
    for (int i = 1; i <= n; ++i)
        tag[i] = i;
    sort(tag + 1, tag + n + 1, cmp);
    int now = 1;
    for (int i = 1; i <= 400; ++i)
    {
        while (now <= n && i == s[tag[now]])
            pq.push(t[tag[now++]]);
        
        if (!pq.empty() && i <= pq.top())
        {
            pq.pop();
            ++ans1;
        }
        while (!pq.empty() && i >= pq.top())
            pq.pop();
    }

    printf("%d\n%d\n", ans1, ans2);
}

int main()
{
    readin();
    solve();
    return 0;
}