У парі (Золото)#11225

У парі (Золото)

1 секунда

128 мегабайтів

Дуже складна

Маємо $n$ корів, розташованих на числовій прямій. Позиція $i$ -ї корови визначається числом $x_{i}$ x_i, а її вага — числом $y_{i}$ y_i.

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

Кожна пара складається з двох різних корів $a$ та $b$ , чиї позиції не далі, ніж на $k$ одна від одної, тобто $∣ x_{a} - x_{b} ∣ \leq k$ |x_a − x_b| \le k.
Кожна корова або входить до складу якоїсь пари, або залишається неспареною.
Групування в пари називається максимальним, якщо жодні дві неспарені корови не можуть утворити пару.

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

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

Вхідні дані

Перший рядок містить $t$ , $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5), $k$ ( $1 \leq k \leq 1 0^{9}$ 1 \le k \le 10^9).

Кожен з наступних $n$ рядків містить $x_{i}$ x_i ( $0 \leq x_{i} \leq 1 0^{9}$ 0 \le x_i \le 10^9) та $y_{i}$ y_i ( $1 \leq y_{i} \leq 1 0^{4}$ 1 \le y_i \le 10^4). Гарантовано, що $0 \leq x_{1} < x_{2} < \dots < x_{n} \leq 1 0^{9}$ 0 \le x_1 < x_2 < \ldots < x_n \le 10^9.

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Приклад 1

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

Приклад 2

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

Приклад 3

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