Вы играете в игру «Монополия++». В этой игре можно купить не более k зданий, каждое из которых будет добавлять к вашему капиталу какую-то сумму. Всего есть выбор из n зданий. Чтобы купить здание i, надо иметь текущий капитал хотя бы ci. После покупки здание добавит в ваш текущий капитал сумму pi.
Изначально ваш капитал равен M. Определите, каким максимальным капиталом можно овладеть к концу игры.
В первой строке дано общее число зданий n и максимальное число зданий, которые можно приобрести k (1 ≤ k ≤ n ≤ 105).
В следующих n строках даны сами здания. Каждое здание задаётся парой ci, pi, оба числа целые неотрицательные и не превосходят 109 по значению.
В последней строке задано число M — ваш стартовый капитал (0 ≤ M ≤ 109).
Выведите единственное число — максимальный конечный капитал, который можно получить.
|
5 3 1 1 3 3 8 10 4 1 1 2 1 |
7 |
|
2 1 1 10 0 20 1 |
21 |
|
2 2 2 2 3 3 1 |
1 |