D. Азтай завсар

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Петя азтай тоонуудад маш их дуртай. Азтай тоо гэдэг нь аравтын бичлэгтээ зөвхөн $4$ ба $7$-ын тоонууд агуулсан тоонуудыг хэлнэ. Жишээлбэл $47, 744, 4$ нь азтай тоонууд бөгөөд $5, 17, 467$ нь биш юм.

Петяд $n$ ширхэг тоон завсар байгаа $[l_1, r_1]$, $[l_2, r_2]$, ..., $[l_n, r_n]$. Үйлдэл бүрдээ Петя ямар нэг завсар сонгож аваад ($i$-р завсар гэе) $[l_i+1, r_i+1]$ юм уу $[l_i-1, r_i-1]$ завсраар солино. Өөрөөр хэлбэл үйлдэл бүрд Петя аль нэг завсрыг нэг нэгжээр зүүн юм уу баруун тийш зөөнө гэсэн үг.

Петя бүх завсарт агуулагдаж байгаа тоог "нийтэч" тоо гэдэг байв. Энэ нь $x$ тоо бүх $i$-н ($1 ≤ i ≤ n$) хувьд $l_i ≤ x ≤ r_i$ нөхцлийг хангаж байвал "нийтэч" гэсэн үг.

Петя хамгийн ихдээ $k$ үйлдэл хийж дуусаад бүх "нийтэч" тоонуудыг тоолдог байв. Хамгийн ихдээ хэдэн "нийтэч" тоо гарган авч чадах вэ?

Оролт

Эхний мөрөнд нийт завсруудын тоо $n$ ($1 ≤ n ≤ 10^5$) ба хамгийн ихдээ хийх үйлдлийн тоо $k$ ($1 ≤ k ≤ 10^{18}$) байна. Дараагийн $n$ мөрөнд мөр бүрд $l_i$ $r_i$ ($1 ≤ l_i ≤ r_i ≤ 10^18$) хос тоонууд өгөгдөнө.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Хариу болох ганц тоо.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
4 7
1 4
6 9
4 7
3 5
Гаралт
1
Оролт
2 7
40 45
47 74
Гаралт
2

Тэмдэглэл

In the first sample Petya shifts the second segment by two units to the left (it turns into $[4; 7]$), after that number $4$ becomes full.

In the second sample Petya shifts the first segment by two units to the right (it turns into $[42; 47]$), and shifts the second segment by three units to the left (it turns into $[44; 71]$), after that numbers $44$ and $47$ become full.

Сэтгэгдлүүдийг ачааллаж байна...