Задача №114565. Сложная задача
У Егора есть большой лист клетчатой бумаги и не менее большое домашнее задание по математике. Егор, как недобросовестный ученик, планирует списать домашнюю работу с сервиса Титан Бета.
Решение задачи Егора в системе Титан Бета состоит из \(n\) формул-шагов, каждую из которых он должен перенести на лист. Разумеется, формулы в листе должны идти по порядку \(~-\) слева направо. Если в какой-то момент написать следующую формулу нельзя \(~-\) её обязательно надо перенести на следующую строку. Но также разрешено делать переносы и в произвольном месте решения, на усмотрение ученика, однако формула должна быть написана целиком на одной строке.
Поскольку в формулах могут возникать дробные выражения, высоты формул бывают разными. Егор относится к формулам, как к бессвязному набору символов, который влезает в какой-то клетчатый прямоугольник; а именно, \(i\)-я формула занимает прямоугольник \(w_i\) клеток в ширину и \(h_i\) клеток в высоту.
Чтобы строки читались аккуратно, Егор выравнивает все формулы, записанные в одной строке, по нижней границе строки. Таким образом, высота строки равна высоте самой высокой формуле строки. Ширина же строки равна суммарной ширине формул в строке. Суммарной высотой решения назовем суммарную высоту всех строк.
Ширина листа бумаги составляет ровно \(m\) клеток. Егора заинтересовало, какую наименьшую высоту может иметь его решение? Поскольку ему надо делать домашнюю работу, то ответ на этот вопрос предстоит найти вам.
В данной задаче ввод устроен необычным образом \(-\) для тестов последней группы часть входного файла вам придется генерировать самостоятельно.
В первой строке вводятся три числа $n$, $m$, $k$ ($1 \le n \le 10^7,\,1 \le m \le 10^{11},\,1 \le k \le \min(500\,000,\,n)$) \(~---\) общее количество формул, ширина листа, количество формул, высота и ширина для которых будут введены далее.
В следующих \(k\) строках вводится по три целых числа \(i_j w_{i_j}, h_{i_j} (1 \le i_j \le n, 1 \le w_{i_j},\,h_{i_j} \le m)\). Первое число \(-\) номер одной из формул Егора. Следующие два числа \(---\) ширина и высота этой формулы соответственно.
Гарантируется, что индексы \(i_j\) возрастают с каждой следующей строкой.
В последней строке вводятся 4 числа \(a,\,b,\,c,\,d (1 \le a,\,c \le \min(10\,000,\,m), $0 \le b,\,d \le m)\)\(~-\) вспомогательные параметры, которые отвечают за генерацию остальных входных данных.
Для тех формул, номера которых не были перечислены во входных данных, высоту и ширину придётся генерировать самостоятельно. А именно, для любого \(i\), не перечисленного во входных данных, \(w_i = ((w_{i-1} \cdot a + b)\ mod\ m) + 1, h_i = ((h_{i-1} \cdot c + d)\ mod\ m) + 1\). Гарантируется, что \(i=1\) присутствует во входных данных (соответственно, размеры всех формул определяются однозначно).
Выведите одно число\(~-\) минимальную высоту листа шириной \(m\), в который получится уместить все формулы.
В первом примере из условия оптимальным вариантом размещения будет тот, при котором первая формула находится на отдельной строке, а вторая и третья\(~-\) на следующей. Таким образом, суммарная высота получается равной \(2 + 3 = 5\) клеткам.
Во втором примере из условия прямоугольники имеют вид \([(2,\,3),\,(1,\,2),\,(3,\,1),\,(2,\,3)]\). Третий прямоугольник обязательно займет целую строку. Четвертая формула, таким образом, займет свою отдельную строчку, а первая и вторая формулы сгруппируются. Получившиеся строки будут вместе занимать \(3 + 1 + 3 = 7\) клеток в высоту.
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Подзадача 0 (0 баллов) тесты из условия.
Подзадача 1 (12 баллов) \( n \le 10, n = k\).
Подзадача 2 (13 баллов) \( n \le 100, n = k\). Необходимые подгруппы: 1.
Подзадача 3 (14 баллов) \( n \le 3\,000, n = k\). Необходимые подгруппы: 1-2.
Подзадача 4 (7 баллов ) \( n \le 500\,000, n = k, h_i \lt h_{i + 1}\).
Подзадача 5 (8 баллов) \( n \le 500\,000, n = k, h_i \gt h_{i + 1}\).
Подзадача 6 (22 балла) \( n \le 500\,000, n = k\). Необходимые подгруппы: 1-5.
Подзадача 7 (22 балла) \( n \le 10^6\). Необходимые подгруппы: 0-6.
Подзадача 8 (2 балла) без дополнительных ограничений. Необходимые подгруппы: 0-7. Offline-проверка
3 3 3 1 1 2 2 2 3 3 1 3 2 2 2 2
5
4 3 1 1 2 3 1 1 1 1
7