Коник#5267
У яскравий ранок великий зелений коник досліджує простору веранду. Він помічає особливо пишну й смачну латочку трави, що росте на протилежному кінці, і вирішує дістатися туди якомога ефективніше.
Коник починає з позиції і хоче дістатися позиції . За один стрибок він може перестрибнути будь-яку цілу кількість сантиметрів, до максимуму . Кожен стрибок коштує коникові одну одиницю енергії. На щастя, майже на всьому шляху росте смачна трава: після кожного стрибка, якщо коник приземляється на таку латочку, він може підкріпитися й відновлює дві одиниці енергії. Однак є певні ділянки шляху, де трава не росте. Якщо коник приземляється в одному з таких відрізків після стрибка, він не відновлює енергію.
Коник знає, що у нього достатньо енергії, щоб досягти мети. Проте він хоче дістатися смачної латочки з якомога більшим запасом енергії. Допоможіть коникові визначити різницю між фінальним і початковим запасом енергії, коли він дістанеться кінця шляху.
Перший рядок містить два цілих числа та (0 \le N \le 1000, 1 \le K \le 1000) — кількість відрізків на шляху без трави та максимальна довжина стрибка відповідно. Кожен з наступних рядків містить по два цілих числа і (0 \le a \le b \le 10^9) — початкову та кінцеву точку кожного такого відрізка. Жодні два відрізки не перетинаються, і всі вони знаходяться між початковою та кінцевою точками шляху, включно. Останній рядок містить одне ціле число (1 \le X \le 10^9) — координата кінцевої точки шляху. Вважаємо, що коник починає з точки .
Виведіть одне ціле число — різницю між фінальним і початковим запасом енергії коника.
Приклад 1