Задача . Paired Up

По сигналу Фермера Джона некоторые из коров формируют пары так, что

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

  Определите интервал возможных сумм весов неспаренных коров. А именно

  • Если \(T=1\), вычислите минимально возможную сумму весов неспаренных коров.
  • Если \(T=2\), вычислите максимально возможную сумму весов неспаренных коров.

  ФОРМАТ ВВОДА (с клавиатуры / stdin):

  Первая строка ввода содержит \(T\), \(N\), \(K\).

  В каждой из последующих \(N\) строк \(i\)-ая строка содержит \(x_i\) и \(y_i\). Гарантируется, что \(0\le x_1< x_2< \cdots< x_N\le 10^9\)

  ФОРМАТ ВЫВОДА (на экран / stdout):

  Выведите минимальную или максимальную возможные суммы весов неспаренных коров.

  
  

  Примеры

  №	Входные данные	Выходные данные
  1	2 5 2 1 2 3 2 4 2 5 1 7 2	6