0046. Sum of Products

Input file name: sumprod.in
Output file name: sumprod.out
Time limit: 1 s
Memory limit: 64 megabytes

Of course you know that there are Ckn 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.


3 2 2 2 3 16

Source: Petrozavodsk training camp, Summer 2002. Conclusive contest
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution

Printable version