在遙遠的植物王國裡面，水果王國與蔬菜王國的交界處，還藏著一個神秘的地區：番茄地帶。自古以來，兩國就一直在爭論著一個問題：到底番茄屬於水果還是蔬菜？在這樣艱困的環境下，番茄地區裡面成立了一座大學：自然番茄大學（Natural Tomato University，NTU），番茄大學有一個時鐘，叫做番茄鐘，以他在每個整點、25 分、30 分、55 分會報時而聞名，據說與當年兩國交戰時的空襲時段有關。

最近，蔬菜週要在自然番茄大學舉行，作為佔了一半大學學生的群體，活動自然非常盛大。

芹菜是這個活動的主辦方的一員，他負責的部分是拔蘿蔔遊戲。遊戲中，地板上有 $N$ 根蘿蔔，每根蘿蔔的深度是 $A_i$，玩家每次可以選一根蘿蔔，並對他拔一次。每次拔取，蘿蔔的深度就會減半並取到整數位，也就是說，一次拔取會使 $ A_i \leftarrow \lfloor \frac{A_i}{2} \rfloor$。

玩家最多總共可以拔 $K$ 次。拔完之後芹菜會計算該玩家的分數。每根蘿蔔有各自的分數 $W_i$，如果拔完之後，第 $i$ 根蘿蔔的深度是 $B_i$，那麼玩家的總分數就是 $\displaystyle \sum_{i=1}^ n B_iW_i$。

現在，芹菜很好奇如果玩家使用最佳策略，則玩家的分數最少是多少。但芹菜最近忙著跟蘿蔔湯合作，因此他把任務交給了你，請你幫他算出這個值，完成之後他會給你最好喝的芹菜蘿蔔湯作為報酬的。