The Final Battle: Maximizing Magical Energy

The final battle has begun. In order to destroy Hogwarts' magical protections, Voldemort must pass through n layers of protection. Each layer has two parameters: \(k\) and \(p\), representing the magic type and energy, respectively. At the \(i\)-th second (when reaching layer \(i\)), he has three choices:

1. Collect the energy from all layers \([1,i]\) whose magic type equals \(k_i\) (i.e. the type of the current layer). The energy gained is \(\sum_{j=1}^{i} \mathbf{1}(k_j = k_i) \cdot p_j\).
2. Collect the energy from the layer with the maximum energy among \([1,i]\), i.e. \(\max_{1 \le j \le i} p_j\).
3. Use a doubling magic. This choice yields no energy at the current second, but the energy collected in the next second is doubled. However, doubling magic cannot be used consecutively, and at most \(m\) uses are allowed.

Note that each layer's energy can be collected repeatedly. Help Voldemort determine the maximum magical energy that can be accumulated after passing through all \(n\) layers.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of layers and the maximum number of doubling magic uses). Each of the next \(n\) lines contains two integers \(k\) and \(p\), describing the magic type and the energy of the layer, respectively.

outputFormat

Output a single integer: the maximum magical energy that can be collected.

sample

3 1
1 3
1 5
2 4

21