В магазин привезли партию из \(n\) товаров (\(n\) — чётное число), \(i\)-й из которых имеет вес \(a_i\). Перед продажей товары нужно расфасовать по упаковкам. После фасовки будет выполнено следующее:
- всего получится \(\frac{n}{2}\) упаковок, в каждой упаковке лежит ровно два товара;
- вес упаковки, в которой лежат товары с индексами \(i\) и \(j\) (\(1 \le i, j \le n\)) будет равен \(a_i + a_j\).
При этом стоимость упаковки веса \(x\) всегда равна \(\left \lfloor\frac{x}{k}\right\rfloor\) бурлей (округление вниз), где \(k\) — фиксированная и заданная величина.
Распределите товары по упаковкам так, чтобы выручка с их продажи была максимальна. Другими словами, составьте такие \(\frac{n}{2}\) пар из заданных товаров, чтобы сумма величин \(\left \lfloor\frac{x_i}{k} \right \rfloor\), где \(x_i\) — вес упаковки с номером \(i\) (\(1 \le i \le \frac{n}{2}\)), была максимальна.
Например, пусть \(n = 6, k = 3\), веса товаров \(a = [3, 2, 7, 1, 4, 8]\). Объединим их в следующие упаковки.
- В первую упаковку положим третий и шестой товар. Её вес будет равен \(a_3 + a_6 = 7 + 8 = 15\). Стоимость упаковки составит \(\left \lfloor\frac{15}{3}\right\rfloor = 5\) бурлей.
- Во вторую упаковку положим первый и пятый товар, вес составит \(a_1 + a_5 = 3 + 4 = 7\). Стоимость упаковки составит \(\left \lfloor\frac{7}{3}\right\rfloor = 2\) бурля.
- В третью упаковку положим второй и четвертый товар, вес составит \(a_2 + a_4 = 2 + 1 = 3\). Стоимость упаковки составит \(\left \lfloor\frac{3}{3}\right\rfloor = 1\) бурль.
При таком распределении итоговая стоимость всех упаковок составит \(5 + 2 + 1 = 8\) бурлей.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите единственное число — максимально возможную суммарную стоимость всех упаковок.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данный можно получить суммарную стоимость, равную \(4\), если в первую упаковку положить первый и второй товар, а во вторую — третий и четвертый.
В третьем наборе входных данных стоимость каждого товара равна \(0\), поэтому суммарная стоимость будет также равна \(0\).
| № | Входные данные | Выходные данные |
|
1
|
6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2
|
8
4
0
2
1
5
|