eolymp
bolt
Try our new interface for solving problems
Problems

K-стороннее домино

K-стороннее домино

Time limit 1.5 second
Memory limit 8 MiB

Стандартный набор домино содержит 28 костяшек. Костяшка представляет собой прямоугольник, разделенный на 2 части. Каждая часть может содержать одно число из множества {0, 1, 2, 3, 4, 5, 6}. При этом числа на обоих частях могут совпадать. В наборе есть все возможные костяшки и никакие две костяшки не содержат одну и ту же пару чисел.

Рассмотрим набор домино, в котором костяшки разделяются на K частей. Числа, которые содержатся на частях костяшек, будут выбираться из некоторого множества A состоящего из N элементов. Две костяшки считаются одинаковыми, если множества чисел, записанных на них, совпадают с учетом кратности. Набор содержит все возможные костяшки без повторений.

Определите количество костяшек в наборе и общую сумму всех чисел на них.

Input data

В первой строке строке задаются два целых числа N, K. Во второй строке задаются числа a_i множества A (1K10^4, 1N10^6, 1a_i10^9). Все a_i различны.

Output data

В единственную строку выведите два числа – количество костяшек в наборе и сумму всех чисел на них.

Examples

Input example #1
7 2
0 1 2 3 4 5 6
Output example #1
28 168
Author Неспирный В.Н.