Футбол#6586

Футбол

1 секунда

64 мегабайти

Дуже легка

Ваш улюблений футбольний клуб бере участь у благодійному турнірі, що є частиною всесвітньої кампанії зі збору коштів для допомоги дітям з обмеженими можливостями. Як і в звичайному турнірі, команда отримує три очки за перемогу і жодного за поразку. Якщо гра завершується внічию, кожна команда отримує по одному очку.

Ваша команда зіграла $N$ матчів у першій фазі турніру, яка щойно завершилася. Лише деякі команди, ті, що набрали більше очок, пройдуть до другої фази турніру. Однак, оскільки головною метою турніру є збір коштів, перед визначенням команд, які пройдуть далі, кожній команді дозволено купити додаткові голи. Ці нові голи враховуються як звичайно забиті і можуть змінити результат будь-якого з матчів, які команда зіграла.

Бюджет вашої команди дозволяє купити до $G$ голів. Чи можете ви визначити максимальну загальну кількість очок, яку ваша команда може отримати після покупки голів, припускаючи, що інші команди не купуватимуть голи?

Вхідні дані

Перша строка містить два цілі числа $N$ ( $1 \leq N \leq 1 0^{5}$ 1 \leq N \leq 10^5) та $G$ ( $0 \leq G \leq 1 0^{6}$ 0 \leq G \leq 10^6), які відповідно представляють кількість матчів, зіграних вашою командою, та кількість голів, які ваша команда може купити. Кожен з наступних $N$ рядків описує результат матчу двома цілими числами $S$ та $R$ ( $0 \leq S, R \leq 100$ 0 \leq S, R \leq 100), які відповідно вказують кількість голів, забитих вашою командою, та отриманих у цьому матчі до покупки голів.

Вихідні дані

Виведіть одне ціле число, яке представляє максимальну загальну кількість очок, яку ваша команда може отримати після покупки голів.

Приклади

Приклад 1