0046. Sum of Products

Имя входного файла:	sumprod.in
Имя выходного файла:	sumprod.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

Of course you know that there are C^k_n ways to select k numbers from a set of n. Given a set of n integer numbers, Anton for each such combination calculates its total product and then sums all products.

For example, if the numbers are (2, 2, 3), k=2 and n=3 he will get 2⋅ 2+2⋅ 3+2⋅ 3=16.

Your task is to calculate the answer he will get.

Input file

The first line of the input file contains two integer numbers n and k (1≤ k≤ n≤ 200). The second one contains n non-negative integer numbers. These numbers will not be greater than 32000.

Output file

Output only one integer number – sum of all products by k.

Examples:

sumprod.in	sumprod.out
3 2 2 2 3	16

Источник: Petrozavodsk training camp, Summer 2002. Conclusive contest
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати