Problem F: Plants vs. Zombies ## Problem F: Plants vs. Zombies

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 2690 Solved: 247

[Submit][Status][Web Board]## Description

You want your plants be more stronger to against the zombies. You have \(n\) plants, each plant has two attributes: height and strength. Crazy Dave has two kinds of fertilizer \(F_h\) and \(F_s\). Each bag of \(F_h\) can make one plant double its height, and each bag of \(F_s\) can make one plant's strength equals its height. Crazy Dave gives you p bags of \(F_h\) and q bags of \(F_s\). You want to maximize the sum of your plants' strength.

More formally, you are given n pair of integers \(<h_i, s_i>\), which indicates the height and strength of the i-th plant. You can use at most p times \(F_h\) and at most q times \(F_s\)

If you give a \(F_h\) to the i-th plant, then \(h_i = h_i * 2\);

If you give a \(F_s\) to the i-th plant, then \(s_i = h_i\).

You want to maximize the \(\sum s_i\)

## Input

The first line of the input contains three integers \(n,p,q\).

For the next \(n\) lines, each line contains two integers \(h_i, s_i\), indicates the height and strength of the i-th plant.

For all cases, \(1 ≤ n ≤ 2*10^5,~0 ≤ p ≤ 20,~0 ≤ q ≤ 2*10^5,~1\leq h_i,s_i \leq 10^9\).

## Output

Print one integer indicates the maximum of \(\sum s_i\).

## Sample Input

2 1 1
10 8
6 1

## Sample Output

21

## HINT

[Submit][Status]