#include <stddef.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdbool.h>
typedef bool ( * less_than_t) (const void * a, const void * b);
void sort_array (void * const array_base, size_t array_size, size_t element_size, less_than_t less_than);
struct struct_TP { size_t T; int32_t P; };
#define MAX_C 1000000
#define MAX_N 2000
#define MAX_T 1500
size_t carnati_N = 0;
int32_t carnati_C = 0;
struct struct_TP carnati_TP[MAX_N];
size_t carnati_K = 0;
int32_t carnati_P[MAX_N];
int64_t carnati_A_values[MAX_T + 1];
size_t carnati_A_begin = 0;
size_t carnati_A_end = 0;
int64_t carnati_answer = 0;
bool less_than_to_sort_increasingly_by_price (const void * a, const void * b) {
return ((*((int32_t const *) a)) < (*((int32_t const *) b)));
}
bool less_than_to_sort_increasingly_by_time (const void * a, const void * b) {
return ((((struct struct_TP const *) a) -> T) < (((struct struct_TP const *) b) -> T));
}
void read_the_input (void) {
(void) freopen("carnati.in", "r", stdin);
size_t index_J = 0;
size_t time_when = 0;
int32_t willingness_to_pay = 0;
(void) scanf("%" "zu" "%" SCNd32 "\n", &carnati_N, &carnati_C);
/* 1 <= carnati_N ≤ MAX_N, 1 ≤ carnati_C ≤ MAX_C. */
while (carnati_N > index_J) {
(void) scanf("%" "zu" "%" SCNd32 "\n", &time_when, &willingness_to_pay);
/* 0 ≤ time_T ≤ MAX_SIZE_ARRAY_A − 1, 0 ≤ willingness_to_pay ≤ 1 000 000 */
carnati_TP[index_J].T = time_when;
carnati_TP[index_J].P = willingness_to_pay;
index_J += 1;
}
}
void collect_the_prices_to_ask (void) {
size_t index_J = 0;
size_t count_K = 0;
while (carnati_N > index_J) {
carnati_P[index_J] = carnati_TP[index_J].P;
index_J += 1;
}
sort_array(carnati_P, carnati_N, sizeof(int32_t), less_than_to_sort_increasingly_by_price);
count_K = 1;
index_J = 1;
while (carnati_N > index_J) {
if (carnati_P[count_K - 1] < carnati_P[index_J]) {
if (count_K < index_J) {
carnati_P[count_K] = carnati_P[index_J];
}
count_K += 1;
}
index_J += 1;
}
carnati_K = count_K;
}
void build_payments_array (int32_t asked_price) {
size_t time_first = MAX_T + 1;
size_t time_last = time_first;
size_t time_when = 0;
int32_t willingness_to_pay = 0;
size_t index_J = 0;
while (carnati_N > index_J) {
willingness_to_pay = carnati_TP[index_J].P;
if (asked_price <= willingness_to_pay) {
time_when = carnati_TP[index_J].T;
if (MAX_T < time_first) {
time_first = time_when;
carnati_A_values[time_first] = 0;
carnati_A_values[time_first] -= carnati_C;
carnati_A_values[time_first] += asked_price;
time_last = time_first;
}
else {
while (time_last < time_when) {
time_last += 1;
carnati_A_values[time_last] = 0;
carnati_A_values[time_last] -= carnati_C;
}
carnati_A_values[time_last] += asked_price;
}
}
index_J += 1;
}
carnati_A_begin = time_first;
carnati_A_end = time_last + 1;
}
int64_t max_subarray_sum (void) {
/**
***
*** Kadane's algorithm, to find the sum of the subarray of max sum.
***
**/
int64_t max_sum = - MAX_C;
int64_t current_sum = 0;
int32_t value_v = 0;
size_t index_T = carnati_A_begin;
while (carnati_A_end > index_T) {
value_v = carnati_A_values[index_T];
if (0 > current_sum) {
current_sum = 0;
}
current_sum += value_v;
if (current_sum > max_sum) {
max_sum = current_sum;
}
index_T += 1;
}
return max_sum;
}
void solve_the_problem (void) {
size_t index_J = 0;
int32_t asked_price = 0;
int64_t max_profit = 0;
int64_t profit = 0;
collect_the_prices_to_ask();
sort_array(carnati_TP, carnati_N, sizeof(struct struct_TP), less_than_to_sort_increasingly_by_time);
while (carnati_K > index_J) {
asked_price = carnati_P[index_J];
build_payments_array(asked_price);
profit = max_subarray_sum();
if (profit > max_profit) {
max_profit = profit;
}
index_J += 1;
}
carnati_answer = max_profit;
}
void write_the_output (void) {
(void) freopen("carnati.out", "wt", stdout);
(void) printf("%" PRId64 "\n", carnati_answer);
}
int main (void) {
read_the_input();
solve_the_problem();
write_the_output();
return 0;
}
void swap_bytes (void * const e, void * const f, size_t num_bytes) {
char * ce = (char *) e;
char * cf = (char *) f;
char ch = 'a';
while (0 < num_bytes) {
ch = *ce; *ce = *cf; *cf = ch;
ce += 1;
cf += 1;
num_bytes -= 1;
}
}
void shift_down (void * const array_base, size_t array_size, size_t element_size, size_t index_J, less_than_t less_than) {
char * const base = (char *) array_base;
size_t limit_down = array_size / 2;
size_t parent = index_J;
size_t child = 0;
while (parent < limit_down) {
child = (parent + parent) + 1;
if ( ((child + 1) < array_size) &&
(less_than(base + child * element_size, base + (child + 1) * element_size)) ) {
child = child + 1;
}
if (less_than(base + parent * element_size, base + child * element_size)) {
swap_bytes(base + parent * element_size, base + child * element_size, element_size);
parent = child;
}
else {
parent = array_size;
}
}
}
void max_heapify (void * const array_base, size_t array_size, size_t element_size, less_than_t less_than) {
size_t index_J = array_size / 2;
while (0 < index_J) {
index_J -= 1;
shift_down(array_base, array_size, element_size, index_J, less_than);
}
}
void sort_max_heap (void * const array_base, size_t array_size, size_t element_size, less_than_t less_than) {
/* It sort the ever increasing tail. */
char * const base = (char *) array_base;
size_t head_size = array_size;
while (1 < head_size) {
swap_bytes(base + 0 * element_size, base + (head_size - 1) * element_size, element_size);
head_size -= 1;
shift_down(array_base, head_size, element_size, 0, less_than);
}
}
void sort_array (void * const array_base, size_t array_size, size_t element_size, less_than_t less_than) {
max_heapify(array_base, array_size, element_size, less_than);
sort_max_heap(array_base, array_size, element_size, less_than);
}
Marius B mgnt