Є \(N\) (\(1\le N\le 10^5\)) корів на числовій прямій. Розташування \(i\)-ої корови задано числом \(x_i\) (\(0 \leq x_i \leq 10^9\)), а вага \(i\)-ої корови заданий числом \(y_i\) (\(1 \leq y_i \leq 10^4\)).

За сигналом Фермера Джона деякі з корів формують пари так, що

• Кожна пара складається з двох різних корів \(a\) і \(b\) чиї розташування не далі \(K\) один від одного (\(1\le K\le 10^9\)); тобто \(|x_a-x_b|\le K\).
• Кожна корова або є частиною деякої пари або не є частиною деякої пари.
• Угруповання в пари називається максимальним, якщо жодні дві з неспарених корів неспроможні утворити пари.

Визначте інтервал можливих сум ваги неспарених корів. А саме

• Якщо \(T=1\), обчисліть мінімально можливу суму ваг неспарених корів.
• Якщо \(T=2\), обчисліть максимально можливу суму ваг неспарених корів.

Формат вхідних даних

Перший рядок введення містить \(T\), \(N\), \(K\).

У кожному з наступних \(N\) рядків \(i\)-ий рядок містить \(x_i\) та \(y_i\). Гарантується, що \(0\le x_1< x_2< \cdots< x_N\le 10^9\)

Формат вихідних даних

Виведіть мінімальну або максимальну можливі суми ваги неспарених корів.

Приклад вхідних даних-1

2 5 2
1 2
3 2
4 2
5 1
7 2

Приклад вихідних даних-1

6

Пояснення до прикладу-1

У цьому прикладі корови \(2\) і \(4\) можуть бути спарені, оскільки відстань між ними
одно \(2\). Це оптимально, оскільки інші спарювання взагалі не можливі:
Корови \(1\) та \(3\) знаходяться на відстані 3.
Корови \(3\) та \(5\) знаходяться на відстані 3.
Корови \(1\) та \(5\) знаходяться на відстані 6.
Сума ваг неспарених корів дорівнює:
\(2 + 2 + 2 = 6\).

Приклад вхідних даних-2

1 5 2
1 2
3 2
4 2
5 1
7 2

Приклад вихідних даних-2

2

Пояснення до прикладу-2

Тут корови \(1\) і \(2\) можуть бути спарені, оскільки вони знаходяться на відстані 2(<=K).
Корови \(4\) і \(5\) також можуть бути спарені, оскільки вони також знаходяться на відстані 2(<=K).
Останнє спарювання оптимально, т.к. неспареної залишається лише корова \(3\), її вага \(2\).

Приклад вхідних даних-3

2 15 7
3 693
10 196
12 182
14 22
15 587
31 773
38 458
39 58
40 583
41 992
84 565
86 897
92 197
96 146
99 785

Приклад вихідних даних-3

2470

Пояснення до прикладу-3

Відповідь цього прикладу дорівнює \(693+992+785=2470\).

Оцінювання

В тестах 4-8 \(T=1\).
В тестах 9-14 \(T=2\) и \(N\le 5000\).
В тестах 15-20 \(T=2\).