Задача №113219. Ловить или не ловить
Владельцы рыболовецкого судна, ведущего промысел на реке Кама, решили в летнем сезоне оптимизировать свой бизнес.
Они получили сезонное разрешение на лов рыбы в \(n\) точках русла реки на расстояниях \(x_1, x_2, \dots , x_n\) километров от устья. При этом в точке с номером \(i\) разрешается выловить не более \(a_i\) тонн рыбы.
Выловленную рыбу можно продавать на m оптовых базах, расположенных вдоль берега реки в точках на расстояниях \(y_1, y_2, \dots , y_m\) километров от устья. При этом база в точке номер \(j\) готова в этом сезоне закупить не более \(b_j\) тонн рыбы по цене \(c_j\) рублей за тонну.
Расстояния от устья до точек вылова и оптовых баз измеряются вдоль русла реки.
Судно отправляется на лов из устья реки и должно вернуться туда же после окончания сезона. В течение сезона судно может произвольным образом плавать вверх и вниз по реке, останавливаясь для лова или продажи рыбы. Грузоподъёмность судна достаточна для перевозки любого количества выловленной рыбы. При удалении от устья судно движется против течения, расходуя на один километр пути топливо стоимостью \(p\) рублей. При перемещении в сторону устья судно движется по течению и поэтому не расходует топлива.
По итогам сезона прибыль за улов будет равна суммарной стоимости проданной рыбы за вычетом суммарной стоимости затраченного топлива.
Требуется написать программу, определяющую максимальную прибыль, которую можно получить за сезон.
Первая строка входных данных содержит три целых числа \(n\), \(m\) и \(p\) — количество точек лова рыбы, количество оптовых баз и стоимость топлива
(\(1 \le n, m \le 500 000; 0 \le p \le 10^9 \)).
Следующие \(n\) строк содержат по два целых числа \(x_i\) и \(a_i\) — расстояние от устья и максимальный улов для каждой точки лова рыбы (\(0 < x_1 < x_2 < \dots < x_n \le 10^9 ; 0 < a_i \le 10^6\) ).
Следующие \(m\) строк содержат по три целых числа \(y_j, b_j, c_j\) — расстояние от устья, максимальное закупаемое количество тонн рыбы и цена закупки за тонну для каждой оптовой базы (\(0 < y_1 < y_2 < \dots < y_m \le 10^9 ; 0 < b_j, c_j \le 10^6\) ).
Выходные данные должны содержать единственное целое число — максимальную возможную прибыль.
Во втором примере оптимальными будут следующие действия. Следует доплыть до точки на расстоянии 6 километров от устья, потратив 600 рублей на топливо, и выловить в ней 5 тонн рыбы. После этого следует спуститься на 1 километр по реке к базе на расстоянии 5 километров от устья и продать выловленную рыбу по цене 2000 рублей за тонну. Затем следует вернуться в устье реки. Суммарная прибыль составит 9400 рублей.
3 2 0 1 5 2 3 4 5 2 2 10 3 6 5
50
2 1 100 6 5 100 4 5 100 2000
9400
3 3 10 1 1 10 100 20 10 2 1000 1 11 50 50 17 50 2
2441