Cupa строит подключенную сеть, используя $n$ компьютеров и один концентратор.

Компьютеры пронумерованы от $1$ до $n$. Каждый компьютер $i$ имеет исходящий провод, который может передать один бит данных на другой конец за $d_i$ миллисекунд.

Концентратор имеет $k$ портов, к которым можно подключить провода компьютера, и каждый компьютер имеет один порт.

Cupa требует, чтобы провод каждого компьютера был подключен к какому-то порту~--- либо в концентраторе, либо в другом компьютере. Также должна быть возможность отправлять данные в концентратор с каждого компьютера напрямую или через другие компьютеры.

Сетевая задержка $t_i$ для каждого компьютера $i$ определяется как время, необходимое для отправки одного бита данных с компьютера $i$ на концентратор. Будем считать, что промежуточным компьютерам не нужно время, чтобы перенаправить полученные данные на свои исходящие провода.

После построения сети Cupa рассчитает сетевую задержку $t_i$ для каждого компьютера $i$. Он хочет, чтобы общая задержка сети для всех компьютеров, т. е. $t_1 + t_2 + \ldots + t_n$, была как можно меньше.

Помогите Cupa построить сеть таким образом, чтобы свести к минимуму общую задержку в сети.