Problem F: Plants vs. Zombies

## Problem F: Plants vs. Zombies

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4965  Solved: 441
[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

[Submit][Status]