12211221 SUSTech Online Judge
Problem 1221 --Excellent power

1221: Excellent power

Time Limit: 15 Sec  Memory Limit: 128 MB
Submit: 2036  Solved: 165
[Submit][Status][Web Board]

Description

In the tale, there was a great wizard at SUSTech called SUSTechDaFaShi with excellent power. With his great power, DFS led a scourge army with \(n\) ultimate soldiers. Each soldier has 2 attributes, hp and attack. What's more, DFS can cast at most \(p\) times of spell1 to make one soldier double its hp, and at most \(q\) times of spell2 to make one soldier's attack equal to its hp. DFS wants to know the maximum sum of the attack of all his soldiers after casting two kinds of spells.

Input

The first line of the input contains three integers \(n, p, q (1\le n \le 200\ 000, 0\le p\le 20, 0\le q\le 200\ 000 )\).

Then \(n\) lines follow, each line contains two integers \(hp_{i}, attack_{i}(1\le hp_{i},attack_{i}\le 1\ 000\ 000\ 000)\), indicates the hp and attack of the ith soldier.

Output

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

Sample Input

2 1 1
10 8
6 1

Sample Output

21

HINT

DFS can choose not to cast any spell.

Source

 

[Submit][Status]