Problem1142--星球人口

1142: 星球人口

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 440  Solved: 159
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI统治了N颗星球,其中第i颗星球上现在有Ai亿人口。每年每颗星球的人口都会增长K亿。从现在开始,每过100年,PIPI会挑选一颗人口最多的星球,消灭其中一半的人口。(假设当时该星球有X亿人口,将只剩下⌊X/2⌋亿人口)
请你计算现在经过了M个100年之后,这N颗星球总计还有多少亿人口。

Input

第一行包含3个整数N, M和K。  

第二行包含N个整数,A1, A2, ... AN。

1 <= N, M <= 100000  

1 <= K <= 100  

1 <= Ai <= 100000

Output

一个整数代表答案

Sample Input

3 3 1  
10 100 200

Sample Output

735

Source/Category

中等 STL