Задача 8. Обработка больших данных ≡

Условие

В научной лаборатории разрабатывается новая архитектура суперкомпьютера, позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^k – 1. Отрезком [L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R, включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является корректным, если его длина (R − L + 1) равна 2ⁱ для некоторого i, а число L делится на 2ⁱ. Например, если 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. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые c₁ ячеек памяти необходимо заполнить значениями v₁, следующие c₂ ячеек — значениями v₂, и так далее, последние c_n ячеек памяти необходимо заполнить значениями v_n, где 1 ≤ v_i ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c₁ = 1, v₁ = 1, c₂ = 2, v₂ = 2, c₃ = 5, v₃ = 1, то итоговое содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для инициализации памяти достаточно трех операций STORE:

1. STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
2. STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
3. STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти определяет минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Формат входных данных

Первая строка входных данных содержит три целых числа: k, n и m.

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа c_i и v_i.

Формат выходных данных

Требуется вывести одно целое число – минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Ограничения

0 ≤ k ≤ 30, 1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹

1 ≤ c_i ≤ 2^k, 1 ≤ v_i ≤ m, c₁ + c₂ + … + c_n = 2^k

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

3 3 2
1 1
2 2
5 1

3