У парі (Золото)
Маємо n корів, розташованих на числовій прямій. Позиція i-ї корови визначається числом x[i], а її вага — числом y[i].
За сигналом Фермера Джона деякі корови можуть утворювати пари за наступними умовами:
Кожна пара складається з двох різних корів a та b, чиї позиції не далі, ніж на k одна від одної, тобто |
x[a]−x[b]| ≤ k.Кожна корова або входить до складу якоїсь пари, або залишається неспареною.
Групування в пари називається максимальним, якщо жодні дві неспарені корови не можуть утворити пару.
Вам потрібно визначити інтервал можливих сум ваг неспарених корів. Зокрема:
Якщо t = 1, обчисліть мінімально можливу суму ваг неспарених корів.
Якщо t = 2, обчисліть максимально можливу суму ваг неспарених корів.
Вхідні дані
Перший рядок містить t, n (1 ≤ n ≤ 10^5), k (1 ≤ k ≤ 10^9).
Кожен з наступних n рядків містить x[i] (0 ≤ x[i] ≤ 10^9) та y[i] (1 ≤ y[i] ≤ 10^4). Гарантовано, що 0 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9.
Вихідні дані
Виведіть мінімальну або максимальну можливу суму ваг неспарених корів.
Приклад 1
У цьому прикладі корови 2 та 4 можуть бути спарені, оскільки відстань між ними дорівнює 2. Це оптимально, оскільки інші спарювання неможливі: корови 1 та 3 знаходяться на відстані 3. Корови 3 та 5 знаходяться на відстані 3. Корови 1 та 5 знаходяться на відстані 6. Сума ваг неспарених корів дорівнює: 2 + 2 + 2 = 6.
Приклад 2
Тут корови 1 та 2 можуть бути спарені, оскільки вони знаходяться на відстані 2 (≤ k). Корови 4 та 5 також можуть бути спарені, оскільки вони також знаходяться на відстані 2 (≤ k). Останнє спарювання оптимальне, оскільки неспареною залишається лише корова 3, її вага 2.
Приклад 3
Відповідь для цього прикладу дорівнює 693 + 992 + 785 = 2470.