13661366 SUSTech Online Judge
Problem 1366 --[Medium II] Divine Spirit and Inner Fire

1366: [Medium II] Divine Spirit and Inner Fire

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1681  Solved: 148
[Submit][Status][Web Board]


Hong raises an army with n Orcs. Each Orc has health-point and attack-point, which can be expressed by two positive integers, hp and atk. Hong is a gifted wizard, who masters two powerful spells. One is Divine Spirit, which can double one Orc's hp. The other is Inner Fire, changing one Orc's atk to be equal to its hp.
Hong can cast Divine Spirit at most p times, and Inner Fire q times. He wants to know the maximum sum of the attack-point of all his Orcs after casting two kinds of spells. (You can cast no spells as you wish.)


The first line of the input contains three integers n,p,q (1 ≤ n ≤ 2*105, 0 ≤ p ≤ 20, 0 ≤ q ≤ 2*105).
Then n lines follow, each line contains two integers hpi ,atki (1 ≤ hpi , atk≤ 109), indicates the health point and attack-point of the i-th Orc.


Print one single integer, the sum of the attack of all the Orcs.

Sample Input

2 1 1
10 8
6 1

Sample Output