В научной лаборатории разрабатывается новая архитектура суперкомпьютера,
позволяющая эффективно обрабатывать большие объемы данных.
Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k– 1. Отрезком
[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,
включительно.
Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является
корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.
Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются
отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,
6] и [7, 7].
Ключевой операцией в новой архитектуре является операция STORE, которая за одно
действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного
отрезка.
Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить
на суперкомпьютере программу обработки данных, но перед её запуском необходимо
инициализировать память определенным образом. А именно: первые с1 ячеек памяти
необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,
последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.
Ученым надо выяснить, какое минимальное количество операций STORE необходимо
выполнить, чтобы проинициализировать память требуемым образом.
Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое
содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для
инициализации памяти достаточно трех операций STORE:
- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],
как и требуется.
Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не
является корректным отрезком памяти.
Требуется написать программу, которая по заданному содержимому памяти
определяет минимальное количество операций STORE, которое необходимо выполнить для
инициализации памяти заданным образом.
Формат входных данных
Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10
5, 1 ≤ m ≤ 109).
Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci
и vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).
Формат выходных данных
Требуется вывести одно целое число – минимальное количество операций STORE,
которое необходимо выполнить для инициализации памяти заданным образом.
| Ввод |
Вывод |
|
3 3 2
1 1
2 2
5 1
|
3 |