D. Налуу замаас хөөрөх

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

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

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

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

Вася $X$ тэнхлэгийн дагуу уралдах нэгэн цанын тэмцээнд оролцож байв. Гараа нь $0$ цэг дээр байх бөгөөд бариа нь $L$ цэг дээр байрлах юм. Өөрөөр хэлбэл нийт зам нь $L$ метр урт байх бөгөөд гарааны цэгээс эхлэн $X$ тэнхлэгийн эерэг чиглэлийн дагуу хөдөлнө. Вася маш сайн бэлдсэн бөгөөд одоо тэрээр нэг секундэд нэг метр зам туулж чадах болжээ.

Түүнчлэн уг уралдааны зам дээр $n$ ширхэг хөөрч болох налуу замууд байх бөгөөд налуу зам болгон нь 4-н ширхэг тоогоор дүрслэгдэнэ:

  • $x_{i}$ нь налуу замын координатыг илэрхийлнэ
  • $d_{i}$ нь хэрэв тэрээр уг налуу замаар хөөрвөл хэдэн метр зам туулахыг илэрхийлнэ
  • $t_{i}$ нь хөөрөлт нь хэдэн секунд үргэлжлэхийг илэрхийлнэ
  • $p_{i}$ нь Вася хэдэн метр замын турш хурдаа авж байж хөөрөхөд бэлэн болохыг илэрхийлнэ. Вася хурдаа авах зуур түүнийг цасан дээгүүр гулгаж байна(өөрөөр хэлбэл тэрээр хөөрөөгүй байх юм) гэж үзэх бөгөөд түүний хурд нь нэг метр/секунд хэвээр байх юм.

Вася $X$ тэнхлэгийн дагуу аль ч чиглэлд явж болох боловч тэрээр гарааны цэгийг өнгөрөн явах нь хориотой юм. Өөрөөр хэлбэл тэрээр $X$ тэнхлэгийн сөрөг тал уруу явж болохгүй. Вася ямар налуу замуудаас хөөрөх болон ямар дарааллаар хөөрөхөө өөрөө сонгох бөгөөд өөрөөр хэлбэл тэрээр өөрийн тулгарсан бүх налуу замууд дээгүүр яван хөөрөх албагүй байх юм. Тодруулбал тэрээр зарим налуу замуудыг орхин явж болно. Мөн $x_{i} + d_{i} ≤ L$ байх бөгөөд өөрөөр хэлбэл Вася агаар дээр хөөрч байхдаа барианы цэгийг өнгөрөн явахгүй байх юм.

Вася налуу замаас хөөрөхдөө зөвхөн $X$ тэнхлэгийн эерэг чиглэлийн дагуу хөөрнө. Илүү дэлгэрэнгүй тайлбарлавал, тэрээр $i$-р налуу замыг хэрэглэх үедээ $x_{i} - p_{i}$ гэсэн цэгээс эхлэн хурдаа авах бөгөөд $x_{i}$ цэг дээрээс эхлэн хөөрөх ба агаар дээр хөөрч явсаар $x_{i} + d_{i}$ гэсэн цэг дээр газардах юм. Мөн тэрээр налуу замуудыг эсрэг чиглэлийн дагуу ашиглаж болохгүй.

Таны даалгавар бол Вася уралдааны замыг туулах хамгийн бага хугацааг секунд нэгжээр олох юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $L$ ($0 ≤ n ≤ 10^{5}$, $1 ≤ L ≤ 10^{9}$) өгөгдөнө. Дараагийн $n$ ширхэг мөрөнд налуу замуудын тайлбар өгөгдөх ба тайлбар болгон нь дан мөрөнд өгөгдөнө. Тайлбар болгон нь 4-н ширхэг сөрөг биш бүхэл тоонууд $x_{i}$, $d_{i}$, $t_{i}$, $p_{i}$ ($0 ≤ x_{i} ≤ L$, $1 ≤ d_{i}, t_{i}, p_{i} ≤ 10^{9}$, $x_{i} + d_{i} ≤ L$)-уудаар өгөгдсөн байна.

Гаралт

Гаралтын эхний мөрөнд Вася уралдааны замыг туулж дуусгахад шаардлагатай хамгийн бага хугацааг секунд нэгжээр хэвлэнэ үү. 2-дахь мөрөнд $k$ тоог хэвлэх ба энэ нь Вася-ын хэрэглэх налуу замуудын тоог илэрхийлнэ. 3-дахь мөрөнд $k$ ширхэг тоо хэвлэх бөгөөд эдгээр нь Вася-ын хэрэглэсэн дарааллын дагуух налуу замуудын дугааруудыг илэрхийлэх юм. Тоо бүрийг яг ганц удаа хэвлэх бөгөөд хооронд нь зайгаар тусгаарласан байна. Мөн налуу замууд нь оролтод өгөгдсөн дарааллынхаа дагуу 1-ээс эхлэн дугаарлагдсан байна.

Орчуулсан: Баатархүү

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

Оролт
2 20
5 10 5 5
4 16 1 7
Гаралт
15
1
1 
Оролт
2 20
9 8 12 6
15 5 1 1
Гаралт
16
1
2 

Тэмдэглэл

Эхний жишээнд Вася 2-р налуу замыг ашиглаж болохгүй юм. Учир нь хэрэв тэрээр уг налуу замыг ашиглавал -3 гэсэн цэгээс эхлэн хурдаа авах хэрэгтэй болох бөгөөд энэ нь бодлогын нөхцөлийг зөрчиж байна. Боломжит хариулт нь 1-р налуу замыг ашиглах бөгөөд үр дүнгийн хугацаа нь: хурд авах цэг хүртэл явах + налуу замаас хөөрөх хүртэл хурдаа авах + хөөрөлтийн хугацаа + барианы цэг хүртэл явах$ = 0 + 5 + 5 + 5 = 15$ болох юм.

2-дахь жишээнд $t_{1} > d_{1}$ учраас Вася 1-р налуу замыг ашиглах нь тохиромжгүй байх юм. Боломжит хариулт нь 2-р налуу замыг сонгох бөгөөд үр дүнгийн хугацаа нь: хурд авах цэг хүртэл явах + налуу замаас хөөрөх хүртэл хурдаа авах + хөөрөлтийн хугацаа + барианы цэг хүртэл явах$ = 14 + 1 + 1 + 0 = 16$ болох юм.

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