#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

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

const int N = 30;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, k, ans;
int segs[N][2], tag[N];

signed main()
{
    read(n, k);
    for (int i = 0; i < n; i ++) read(segs[i][0], segs[i][1]);
    for (int state = 0; state < 1 << n; state ++)
    {
        if (__builtin_popcount(state) != k) continue;

        int res = 0;
        for (int i = 0; i < n; i ++)
            if (state >> i & 1)
                for (int j = segs[i][0]; j <= segs[i][1]; j ++) tag[j] ++;
        for (int i = 1; i <= n; i ++)
            if (tag[i]) res ++, tag[i] = 0;
        ans = max(ans, res);    
    }
    cout << ans << '\n';
    return 0;
}