/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
あるプログラミングコンテストでは N 問の問題が出題され、そのうち i 問目に正解すると A_i 点が与えられます。
この N 問の中からちょうど K 問を選んで解くことを考えます。
「選んだ問題を全て解いた時に得られる合計得点」を全ての選び方に対して求めたとき、その和はいくつになりますか？
制約
- 入力は全て整数
- 1 \le K \le N \le 8
- 1 \le A_i \le 2718
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
4 2 100 200 300 400
出力例 1
3000
このコンテストでは 4 問の問題が出題され、このうち 2 問を解くことを考えます。選び方は以下の 6 通りです。
- 1 問目と 2 問目を解く。得られる合計得点は 300 点である。
- 1 問目と 3 問目を解く。得られる合計得点は 400 点である。
- 1 問目と 4 問目を解く。得られる合計得点は 500 点である。
- 2 問目と 3 問目を解く。得られる合計得点は 500 点である。
- 2 問目と 4 問目を解く。得られる合計得点は 600 点である。
- 3 問目と 4 問目を解く。得られる合計得点は 700 点である。
これらの合計得点の和は 3000 点です。
入力例 2
1 1 2718
出力例 2
2718
入力例 3
8 4 597 1035 2048 994 1843 601 7 659
出力例 3
272440
Problem Statement
In a certain programming contest, N problems are set, and if you answer the i-th problem correctly, you are given A_i points.
Consider choosing and solving exactly K problems out of these N problems.
When you calculate the "total score obtained when all the selected problems are solved" for all ways of choosing problems, what is the sum of those total scores?
Constraints
- All input values are integers.
- 1 \le K \le N \le 8
- 1 \le A_i \le 2718
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
4 2 100 200 300 400
Sample Output 1
3000
In this contest, 4 problems are set, and we consider solving 2 of them. There are 6 ways to choose the problems as follows.
- Solve the 1-st and 2-nd problems. The total score obtained is 300 points.
- Solve the 1-st and 3-rd problems. The total score obtained is 400 points.
- Solve the 1-st and 4-th problems. The total score obtained is 500 points.
- Solve the 2-nd and 3-rd problems. The total score obtained is 500 points.
- Solve the 2-nd and 4-th problems. The total score obtained is 600 points.
- Solve the 3-rd and 4-th problems. The total score obtained is 700 points.
The sum of these total scores is 3000 points.
Sample Input 2
1 1 2718
Sample Output 2
2718
Sample Input 3
8 4 597 1035 2048 994 1843 601 7 659
Sample Output 3
272440