/**
* JOI 2019 Spring Camp - Cake 3
* * Problem Analysis:
* We need to choose M pieces. Let the chosen pieces be sorted by Color: P_1, P_2, ..., P_M.
* The beauty is sum(V) - sum(|C_diff|).
* The sum of color differences in a circle for sorted colors is 2 * (C_max - C_min).
* * Strategy:
* 1. Sort all pieces by Color C.
* 2. We need to select a range [i, j] in the sorted array such that:
* - The pieces i and j are the min and max color boundaries.
* - We select M pieces total from the range [i, j].
* - To maximize beauty, we must pick the M pieces with the largest Values V within [i, j].
* 3. The objective function for a fixed range [i, j] (where j >= i + M - 1):
* f(i, j) = SumTopM(i, j) - 2 * (C[j] - C[i])
* 4. We use Divide and Conquer Optimization.
* solve(i_start, i_end, j_start, j_end) computes the best j for i in [i_start, i_end].
* We maintain a global Segment Tree that tracks the values in the current window [curr_L, curr_R].
* * Complexity: O(N * log^2 N)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// Structure to represent a piece of cake
struct Piece {
long long v, c;
int original_id;
};
int N, M;
vector<Piece> pieces;
vector<long long> v_coords; // For coordinate compression of V
// Segment Tree to maintain counts and sums of V values
// We use coordinate compression on V values, so the tree size is N.
const int MAXN = 200005;
long long seg_count[4 * MAXN];
long long seg_sum[4 * MAXN];
// Add a value (by its compressed index/rank) to the segment tree
void update(int node, int start, int end, int idx, int val_cnt, long long val_amount) {
if (start == end) {
seg_count[node] += val_cnt;
seg_sum[node] += val_amount; // If val_cnt is 1, we add real_value; if -1, we subtract
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update(node * 2, start, mid, idx, val_cnt, val_amount);
else update(node * 2 + 1, mid + 1, end, idx, val_cnt, val_amount);
seg_count[node] = seg_count[node * 2] + seg_count[node * 2 + 1];
seg_sum[node] = seg_sum[node * 2] + seg_sum[node * 2 + 1];
}
// Query the sum of the k largest values in the segment tree
long long query(int node, int start, int end, int k) {
if (k <= 0) return 0;
if (seg_count[node] <= k) return seg_sum[node]; // Take everything
if (start == end) {
// We are at a leaf, we need 'k' items from here.
// The value at this leaf is seg_sum[node] / seg_count[node] (conceptually)
// Since all items at a leaf are identical in compressed value:
long long single_val = seg_sum[node] / seg_count[node];
return single_val * k;
}
int mid = (start + end) / 2;
// Right child has larger values (since we compressed V such that larger index = larger V)
if (seg_count[node * 2 + 1] >= k) {
return query(node * 2 + 1, mid + 1, end, k);
} else {
return seg_sum[node * 2 + 1] + query(node * 2, start, mid, k - seg_count[node * 2 + 1]);
}
}
// Global pointers for the current range covered by the segment tree
int cur_L = 1;
int cur_R = 0;
// Function to move the segment tree range to [L, R]
void move_range(int L, int R) {
// Extend or shrink R
while (cur_R < R) {
cur_R++;
// Identify the rank of the V value at cur_R
int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_R].v) - v_coords.begin();
update(1, 0, N - 1, rank, 1, pieces[cur_R].v);
}
while (cur_R > R) {
int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_R].v) - v_coords.begin();
update(1, 0, N - 1, rank, -1, -pieces[cur_R].v);
cur_R--;
}
// Extend or shrink L
while (cur_L > L) {
cur_L--;
int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_L].v) - v_coords.begin();
update(1, 0, N - 1, rank, 1, pieces[cur_L].v);
}
while (cur_L < L) {
int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_L].v) - v_coords.begin();
update(1, 0, N - 1, rank, -1, -pieces[cur_L].v);
cur_L++;
}
}
long long max_beauty = -2e18; // Initialize with a very small number
// Divide and Conquer function
// Computes the optimal j for each i in [i_start, i_end], knowing optimal j is in [j_start, j_end]
void solve(int i_start, int i_end, int j_start, int j_end) {
if (i_start > i_end) return;
int i_mid = (i_start + i_end) / 2;
int best_j = -1;
long long current_max = -4e18;
// We need to iterate j from max(j_start, i_mid + M - 1) to j_end
int start_scan = max(j_start, i_mid + M - 1);
// Evaluate for i_mid
// We iterate j and find the best one for this specific i_mid
for (int j = start_scan; j <= j_end; ++j) {
move_range(i_mid, j); // Adjust seg tree to [i_mid, j]
long long sum_top_m = query(1, 0, N - 1, M);
long long beauty = sum_top_m - 2 * (pieces[j].c - pieces[i_mid].c);
if (beauty > current_max) {
current_max = beauty;
best_j = j;
}
}
if (best_j != -1) {
max_beauty = max(max_beauty, current_max);
} else {
// If no valid j found (e.g. range too small), we still need a valid best_j for recursion bounds.
// Logic suggests best_j should be at least start_scan.
best_j = j_start;
}
// Recursive calls
// For i < i_mid, optimal j is <= best_j
solve(i_start, i_mid - 1, j_start, best_j);
// For i > i_mid, optimal j is >= best_j
solve(i_mid + 1, i_end, best_j, j_end);
}
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> M)) return 0;
pieces.resize(N + 1); // 1-based indexing for convenience in logic
for (int i = 1; i <= N; ++i) {
cin >> pieces[i].v >> pieces[i].c;
v_coords.push_back(pieces[i].v);
}
// 1. Sort pieces by Color C
sort(pieces.begin() + 1, pieces.end(), [](const Piece& a, const Piece& b) {
return a.c < b.c;
});
// 2. Coordinate Compression for V values
sort(v_coords.begin(), v_coords.end());
v_coords.erase(unique(v_coords.begin(), v_coords.end()), v_coords.end());
// 3. Divide and Conquer
// i can range from 1 to N - M + 1
// j can range from M to N
// We initialize pointers for seg tree logic
cur_L = 1;
cur_R = 0;
solve(1, N - M + 1, M, N);
cout << max_beauty << endl;
return 0;
}
