{"raw_statement":[{"iden":"problem statement","content":"Takahashi is going to buy $N$ items one by one.\nThe price of the $i$\\-th item he buys is $A_i$ yen (the currency of Japan).\nHe has $M$ discount tickets, and he can use any number of them when buying an item.\nIf $Y$ tickets are used when buying an item priced $X$ yen, he can get the item for $\\frac{X}{2^Y}$ (rounded down to the nearest integer) yen.\nWhat is the minimum amount of money required to buy all the items?"},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N, M \\leq 10^5$\n*   $1 \\leq A_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $...$ $A_N$"},{"iden":"sample input 1","content":"3 3\n2 13 8"},{"iden":"sample output 1","content":"9\n\nWe can buy all the items for $9$ yen, as follows:\n\n*   Buy the $1$\\-st item for $2$ yen without tickets.\n*   Buy the $2$\\-nd item for $3$ yen with $2$ tickets.\n*   Buy the $3$\\-rd item for $4$ yen with $1$ ticket."},{"iden":"sample input 2","content":"4 4\n1 9 3 5"},{"iden":"sample output 2","content":"6"},{"iden":"sample input 3","content":"1 100000\n1000000000"},{"iden":"sample output 3","content":"0\n\nWe can buy the item priced $1000000000$ yen for $0$ yen with $100000$ tickets."},{"iden":"sample input 4","content":"10 1\n1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"},{"iden":"sample output 4","content":"9500000000"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}