B. Бооцоо

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

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

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

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

Олонд хүндлэгдсэн бизнесмэн Никита Челябинск хотод "Boss" хэмээх нууцлаг нэрээр амьдарч байв. Нэгэн удаа Никита өөрийн найз Алекс-ын хамт зуны биатлонын дэлхийн аварга шалгаруулах тэмцээн үзэхээр шийджээ. Никита олонд маш хүндлэгдсэн хүн учраас тэмцээн дээр очмогц түүнд нэгээс ихгүй оролцогч дээр бооцоо болгон тавьж болдог нэг хясаа өгчээ.

Уг тэмцээнд бооцоогоо тавихаас өмнө дүрмүүдийг сурах хэрэгтэй байв: Уралдаан нь ижил урттай $n$ хэсгээс тогтох ба $m$ ширхэг тамирчин тэмцээнд оролцож байв. Тамирчид нь $1$-ээс $m$ хүртэл дугаарлагдсан байх бөгөөд тамирчин бүрийн хувьд дараах мэдээллүүд мэдэгдэж байв:

  • $l_{i}$ -- гарааны хэсгийн дугаар,
  • $r_{i}$ -- барианы хэсгийн дугаар ($l_{i} ≤ r_{i}$),
  • $t_{i}$ -- уг тамирчин замын нэг хэсгийг туулахад шаардагдах хугацаа,
  • $c_{i}$ -- рубль-ээр өгөгдөх орлого. Хэрэв $i$-р тамирчин нь аль нэг хэсэгт түрүүлбэл уг тамирчин дээр бооцоогоо тавьсан хүний хожих мөнгө буюу орлого тус тус мэдэгдэж байв.

$i$-р тамирчин нь $l_{i}$ дугаартай хэсгээс $r_{i}$ дугаартай хэсэг хүртэлх (эдгээр хэсгүүд нь мөн орно) бүх хэсгүүдээр явж өнгөрөх юм. Иймд тухайн тамирчин нь нийт замаа $(r_{i} - l_{i} + 1)*t_{i}$ нэгж хугацаанд туулах ажээ. Мөн түүнчлэн хэсэг бүрийг тэрээр яг $t_{i}$ нэгж хугацаанд туулж байгаа бөгөөд тухайн тамирчин нь $k$ ширхэг хэсэгт түрүүлсэн бол уг тамирчин дээр бооцоогоо тавьсан хүн $k*c_{i}$ рубль хожих юм.

Хэсэг бүрийн хувьд тухайн хэсгийн ялагч нь бусад хэсгээс үл хамааран дараах байдлаар тодорхойлогдох юм: Хэрэв уг хэсэгт дор хаяж нэг ширхэг тамирчин уралдсан байвал тэдгээрийн дундаас уг хэсгийг хамгийн бага хугацаанд туулсан тамирчин нь уг хэсгийн ялагч болох юм (уг хэсгийг туулахдаа хамгийн бага хугацаа зарцуулсан тамирчин). Хэрэв хамгийн бага хугацаа зарцуулсан олон тамирчин байвал тэдгээрийн хамгийн бага дугаартай тамирчин нь ялагч болно. Хэрэв уг хэсэгт ямар ч тамирчин уралдаагүй байвал уг хэсгийг ялагч нь тодрохгүй ажээ. Түүнчлэн бид уг тэмцээнд оролцогчид нь бүгд тогтмол хурдаар хөдөлнө гэж үзэх юм.

Мөн Никита аль ч хэсэг дээр бооцоо тавьж болох бөгөөд тухайн хэсгийн аль ч тамирчин дээр бооцоогоо тавьж болох юм.

Та эдгээр найзуудад туслан боломжит хамгийн их орлогын (бооцоо тавин хожих мөнгөн дүн) хэмжээг олж өгнө үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 100$) өгөгдөнө. Дараагийн $m$ мөрийн мөр болгонд 4 ширхэг бүхэл тоо $l_{i}$, $r_{i}$, $t_{i}$, $c_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$, $1 ≤ t_{i}, c_{i} ≤ 1000$) өгөгдөнө.

Гаралт

Эдгээр найзуудын олж болох боломжит хамгийн их орлогын хэмжээг рубль-ээр илэрхийлсэн утгыг хэвлэнэ үү. Эдгээр $n$ хэсгийн хэсэг болгоны хувьд нэгээс илүү тамирчин дээр бооцоогоо тавьж болохгүй болохыг анхаарна уу.

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

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

Оролт
4 4
1 4 20 5
1 3 21 10
3 3 4 30
3 4 4 20
Гаралт
60
Оролт
8 4
1 5 24 10
2 4 6 15
4 6 30 50
6 7 4 20
Гаралт
105

Тэмдэглэл

Эхний жишээнд оновчтой бооцоо тавилт нь: 1-ээс 2 хүртэлх хэсгүүдэд 1-р тамирчин дээр, 3-р хэсэг дээр 3-р тамирчин дээр, 4-р хэсэг дээр 4-р тамирчин дээр тус тус бооцоо тавих юм. Ингэснээр 1-р хэсгээс 5 рубль, 2-р хэсгээс 5 рубль, 3-р хэсгээс 30 рубль, 4-р хэсгээс 20 рубль хожих бөгөөд нийт 60 рубль олох юм.

2-дахь жишээний оновчтой бооцоо тавилт нь: 1 болон 5-р хэсгүүдэд 1-р тамирчин дээр, 2-4 хүртэлх хэсгүүд дээр 2-р тамирчин дээр, 6-аас 7 хүртэлх хэсгүүд дээр 4-р тамирчин дээр бооцоо тавих юм. Харин 8-р хэсэгт ямар ч ялагч байхгүй байна. Ингэснээр 1-р хэсгээс 10 рубль, 2 3 4-р хэсгүүдээс тус бүр 15 рубль, 5-р хэсгээс 10 рубль, 6 7-р хэсгүүдээс тус бүр 20 рубль хожих бөгөөд нийт 105 рубль олох юм.

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