#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, D;
vector<int> A, B;
int max_score = 0;

void dfs(int day, vector<bool> used, int score) {
    if (day == D) {
        max_score = max(max_score, score);
        return;
    }

    for (int L = 1; L <= N; ++L) {
        // Lấy danh sách gà còn sống từ 1 đến L
        vector<int> alive;
        for (int i = 0; i < L; ++i) {
            if (!used[i]) alive.push_back(i);
        }

        int K = alive.size();
        // Thử mọi cách chọn: 2^K tổ hợp trứng/thịt
        for (int mask = 0; mask < (1 << K); ++mask) {
            vector<bool> new_used = used;
            int gain = 0;
            for (int i = 0; i < K; ++i) {
                int g = alive[i];
                if ((mask >> i) & 1) {
                    // Làm thịt
                    gain += B[g];
                    new_used[g] = true;
                } else {
                    // Đẻ trứng
                    gain += A[g];
                }
            }
            dfs(day + 1, new_used, score + gain);
        }
    }
}

int main() {
    cin >> N >> D;
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; ++i) {cin >> A[i]>>B[i];}

    vector<bool> used(N, false);
    dfs(0, used, 0);

    cout << max_score << endl;
    return 0;
}