Problem E: [Medium II] Divine Spirit and Inner Fire

Problem E: [Medium II] Divine Spirit and Inner Fire

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1668  Solved: 147
[Submit][Status][Web Board]

Description

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.)

Input

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.

Output

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

Sample Input

2 1 1
10 8
6 1

Sample Output

21

HINT

[Submit][Status]