D. Похищение чертежей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В руки повстанцев случайно попал план сверхсекретного исследовательского полигона, созданного на одной из дальних планет для нужд Галактической Империи. По предположению повстанцев на территории этого полигона ведется разработка нового смертоносного оружия. Полигон состоит из n ракетных шахт, соединенных двусторонними подземными переходами. К переходам примыкают лаборатории, в которых и проводятся исследования. Разумеется, переходы тщательно охраняются: переход между шахтами i и j патрулируют ci, j боевых дроидов.

Изучая план полигона, повстанцы обратили внимание на его необычную структуру. Оказалось, что для любого k-элементного множества шахт S существует ровно одна шахта, напрямую соединенная переходом с каждой шахтой из S (будем называть эту шахту соседней с S). С учетом этого повстанцы приняли решение провести разведывательную операцию на полигоне следующим образом:

  1. выбирается k-элементное множество шахт S;
  2. в каждую шахту из S с воздуха высаживается группа разведчиков;
  3. каждая группа двигается по соответствующему переходу в шахту, соседнюю с S, попутно осматривая лаборатории на предмет наличия чертежей оружия;
  4. в шахте, соседней с S, группы поднимаются на корабль и улетают.

Опасностью операции назовем суммарное количество дроидов, патрулирующих переходы, через которые пройдут разведчики. Очевидно, опасность операции зависит только от способа выбора множества S. Повстанцы еще не решили, в какие именно шахты будут высаживаться разведчики, однако они хотят начать подготовку вооружения для разведывательных групп уже сейчас. Для этого повстанцам нужно знать, каково среднее арифметическое опасностей операций, соответствующих всем возможным способам выбора множества S. Решите эту задачу, чтобы помочь повстанцам защитить идеалы Республики!

Входные данные

В первой строке записано два целых числа n и k (2 ≤ n ≤ 2000, 1 ≤ k ≤ n - 1) — количество шахт и количество разведывательных групп соответственно. В следующих n - 1 строках описывается план полигона: i-ая из этих строк содержит n - i целых чисел ci, i + 1, ci, i + 2, ..., ci, n — количество дроидов, патрулирующих соответствующие переходы (-1 ≤ ci, j ≤ 109; если ci, j =  -1, то перехода между шахтами i и j нет). Все переходы являются двунаправленными, то есть можно считать, что ci, j = cj, i. Переходов, соединяющих шахту саму с собой, не существует. Гарантируется, что план полигона удовлетворяет условию задачи.

Выходные данные

Выведите среднюю опасность разведывательной операции, округленную вниз до целого числа. Обратите внимание, что при указанных ограничениях ответ на задачу всегда помещается в стандартный целочисленный 64-битный тип данных.

Пожалуйста, не используйте спецификатор %lld для вывода 64-битных чисел на С++. Рекомендуется использовать поток cout или спецификатор %I64d.

Примеры
Входные данные
6 1
-1 -1 -1 8 -1
-1 5 -1 -1
-1 -1 3
-1 -1
-1
Выходные данные
5
Входные данные
3 2
10 0
11
Выходные данные
14
Примечание

В первом примере существует 6 одноэлементных множеств шахт. Для множеств {1}, {5} опасность операции составит 8, для множеств {3}, {6} — 3, для множеств {2}, {4} — 5. Среднее арифметическое равно .

Во втором примере существует 3 двухэлементных множества шахт: {1, 3} (опасность равна 21), {1, 2} (опасность равна 11), {2, 3} (опасность равна 10). Средняя опасность операции равна .