Есть заснеженная прямая дорога длины \(L\). Надо почистить.

Есть \(N\) снегоуборочных машин, \(i-ый\) машина в гараже на \(a_i\) километре дороги. За каждый километр машина потребляет \(k_i\) монет.

После завершения очистки, машины должны вернуться обратно на свои места. Машины не должны останавливаться на вершинах, и должны закончить свою работу и вернуться в гараж через \(T\) минут.

Каждая машина может проехать не более 1 километра в минуту, независимо от того, производится ли уборка снег или нет.

Рассчитайте наименьшую стоимость уборки дороги.

Входные данные

Первая строка содержит три целых числа: количество машин \(N\), длина дороги \(L\) и количество минут \(T\), в течение которых дорога должна быть очищена, и машины должны добраться до гаража.

Далее \(N\) пар чисел.

\(a_i\), \(k_i\) - во сколько километров от начала участка дороги находится гараж для \(i\) машины, стоимость одного километра машины. (\(a_i < a_{i+1}\))

\(1 \le N, L \le 10000\), \(1 \le T \le 1000\)

\(0 \le a_i \le L\), \(0 \le k_i \le 1000\)

Выходные данные

Если через \(T\) минут невозможно очистить всю дорогу, выведите слово "NO" (без кавычек).

Иначе выведите наименьшую стоимость уборки.

Система оценивания

Задача состоит из семи подзадач:

1. Примеры из условия. Оценивается в 0 баллов.

2. \(T = 2\). Оценивается в 8 баллов.

3. \(k_i = 1\). Оценивается в 8 баллов.

4. \(N, L, T \le 50\). Оценивается в 11 баллов.

5. \(N, L \le 1000, T \le 100\). Оценивается в 23 балла.

6. \(T\) - четное число. Оценивается в 38 баллов.

7. Ограничения из условия. Оценивается в 12 баллов.

Примеры

Ввод 1

2 5 6
0 2
3 1

Ответ 1

14

Ввод 2

2 3 5
0 2
3 1

Ответ 2

7

Примечания

Первый тест:

Первая машина очищает первые 2 километра и возвращается (2 + 2 = 4 минут, 4 * 2 = 8 монет). Вторая машина проходит один километр до начала дороги, потом 3 километра до конца дороги и в гараж обратно (1 + 3 + 2 = 6 минут, 6 * 1 = 6 монет).

Цена за обе машины составляет 8 + 6 = 14 монет.

Второй тест:

Первая машина чистит первые пол километра и возвращается (0.5 + 0.5 = 1 минута, 1 * 2 = 2 монет).

Вторая машина едет на 2.5 километр в направлении начала дороги и обратно (2.5 + 2.5 = 5 минут, 5 * 1 = 5 монет).

Стоимость использования обеих машин составляет 2 + 5 = 7 монет.