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

Автор:Центральная предметно-методическая комиссия   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

Суперкомпьютер имеет 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. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые c1 ячеек памяти необходимо заполнить значениями 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:

  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-я из этих строк содержит числа ci и vi.

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

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

Ограничения

0 ≤ k ≤ 30, 1 ≤ n ≤ 105, 1 ≤ m ≤ 109

1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
knm
1150 ≤ k ≤ 31 ≤ n ≤ 81 ≤ m ≤ 8баллы
2150 ≤ k ≤ 191 ≤ n ≤ 1051 ≤ m ≤ 101баллы
3150 ≤ k ≤ 301 ≤ n ≤ 1051 ≤ m ≤ 101, 2баллы
4100 ≤ k ≤ 301 ≤ n ≤ 1051 ≤ m ≤ 501, 2, 3баллы
5150 ≤ k ≤ 191 ≤ n ≤ 1051 ≤ m ≤ 1091, 2баллы
6300 ≤ k ≤ 301 ≤ n ≤ 1051 ≤ m ≤ 1091 − 5баллы

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

Стандартный вход Стандартный выход
1
3 3 2
1 1
2 2
5 1
3

0.095s 0.019s 15