Задача . E. Максимизация цен

В магазин привезли партию из \(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\) бурлей.