E. Туслагч

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

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

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

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

Итгэмээргүй боловч ОхВордийн их сургуульд шалгалтын үе эхэлчихэж. Бүүр ч итгэмээргүй нь Валера улирлын турш маш сайн сурсан учир шалгалтын үеэс өмнө бүх тестээ давчихсан. Тэр одоо завтай байгаа ба ангийн хүүхдүүддээ бодлого бодож өгч мөнгө олохыг хүсч байна. Тэр туслаж чадах хичээлүүдийн жагсаалт гаргасан. Валера ангийнхаа $n$ хүүхэдтэй ярилцсанаар Валера тэдний тухай дараах мэдээллийг олсон: тэдгээрийн нэг бүр нь ямар хичээл дээр шалгалттай, шалгалтын хугацаа ба Валерагийн тусламжинд зориулж хүн бүрийн төлөхөд бэлэн байгаа мөнгөний хэмжээ.

Энэ мэдээлэл дээр үндэслэн Валера цагийн хуваарь зурахаар шийдсэн ба үүний дагуу ангийнхандаа бодлого бодож өгч тусална. Мэдээж Валера өдөр шөнөгүй бодлого бодож чадахгүй учир шалгалтын үеийн турш өдөр бүрийн хамгийн тохиромжтой дарааллыг олсон. Валера хугацааны хэсгүүдийг унтах, өглөөний цай, өдрийн хоол ба оройн хоолд хуваарилсан. Үлдсэн цагт нь тэр ажиллаж чадна.

Мэдээж Валери оюутнуудад зөвхөн жагсаалт дээр байгаа хичээлүүдэд нь л туслаж чадна. Валератай ярьсан бүх оюутнууд ялгаатай боловч нэг төрлийн бодлоготой байсан учир Валера $list_{i}$ хичээлийн дурын бодлогыг $t_{i}$ минутанд бодож чадна.

Мөн түүнчлэн хэрвээ Валера нэг бодлого эхлүүлсэн бол тэр зөвхөн унтах эсвэл хоол идэхдээ л завсарлаж болно гэхдээ өмнөх нэгийгээ дуусгаагүй шинэ бодлого эхлүүлж чадахгүй. Бодлогыг бодсон даруйдаа Валера харгалзах оюутанруу Интернетээр илгээж чадна.

Хэрвээ уг оюутны шалгалт хараахан эхлээгүй байгаа бол тэр үүнийг хуулан шалгалттаа амжилттай өгч чадах ба Валерад амласан мөнгөө төлнө. Валерад бага цаг байгаа учир тэр таныг Валерад хамгийн их ашиг авчрах бодлого бодох дарааллыг олдог програм бичихийг хүсч байна.

Оролт

Эхний мөрөнд бүхэл тоон утгууд $m, n, k$ ($1 ≤ m, n ≤ 100$, $1 ≤ k ≤ 30$) байх ба жагсаалтанд байгаа хичээлүүдийн хэмжээ, Валерагийн ажил олгогчдын хэмжээ ба шалгалтын үеийн хугацаа өдрөөр байна.

Дараагийн $m$ мөрөнд хичээлүүдийн нэр $list_{i}$ ($list_{i}$ нь хамгийн ихдээ 32 Латин цагаан толгойн жижиг үсгүүдээс бүрдэх хоосон биш тэмдэгт мөр) байна. Ямар ч хоёр хичээл ижил биш.

$(m + 2)$-р мөрөнд $m$ бүхэл тоон утга $t_{i}$ ($1 ≤ t_{i} ≤ 1000$) байх ба $i$-р хичээлийн бодлогуудыг бодоход Валерагийн зарцуулах хугацаа минутаар байна. Дараагийн дөрвөн мөрөнд харгалзан унтах, өглөөний цай, өдрийн хоол, оройн хоолонд зарцуулах хугацааны хэсгүүд байна.

Мөр бүр $H1:M1-H2:M2$ хэвтэй байх ба энд $00$ ≤ $ H1, H2$ $ ≤ 23$, $00 ≤ $ $M1$, $M2$ $ ≤ 59$ байна. $H1:M1$ цаг нь Валерагийн нэг үйлдлийн эхний минутыг заана харин $H2:M2$ цаг нь уг үйлдлийн сүүлийн минутыг заана. Ямар ч хоёр хугацааны хэсэг огтлолцохгүй. Валера шөнө дундаас өмнө унтах ба өглөөний цайнаасаа өмнө босно мөн өдрийн хоолноос өмнө өглөөний цайгаа дуусгах ба оройн хоолноос өмнө өдрийн хоолоо дуусгах ба унтахаасаа өмнө оройн хоолоо дуусгах нь тодорхой. Эдгээр бүх үйлдэл нь нэг өдрөөс бага хугацаанд үргэлжлэх боловч нэг минутаас бага байж болохгүй. Үйлдэл бүрийн эхлэх болон дуусах цаг цуг ба нэг өдөр байна. Гэвч Валерад бодлого бодох цаг гарахгүй байж болно.

Дараагийн $n$ мөр бүрт оюутнуудын тайлбар байна. Оюутан бүрийн хувьд дараах зүйлс мэдэгдэнэ: түүний шалгалттай хичээл $s_{i}$ ($s_{i}$ нь хамгийн ихдээ 32 Латин цагаан толгойн жижиг үсгээс бүрдэнэ), шалгалттай өдрийн индекс $d_{i}$ ($1 ≤ d_{i} ≤ k$), шалгалтын цаг $time_{i}$ ба Валерад төлөхөд бэлэн мөнгөний хэмжээ $c_{i}$ ($0 ≤ c_{i} ≤ 10^{6}$, $c_{i}$ нь бүхэл тоо байна). Шалгалтын цаг $time_{i}$ нь $HH:MM$ хэвтэй байх ба энд $00 ≤ $ $HH$ $ ≤ 23$, $00 ≤$ $ MM$ $ ≤ 59$ байна. Хэрвээ Валера харгалзах оюутны шалгалт эхлэхээс илэрхий өмнө бодлогыг бодож дуусгавал мөнгөө авах болно.

Гаралт

Гаралтын эхний мөрөнд Валерагийн авч чадах хамгийн их ашгийг хэвлэ. Хоёр дахь мөрөнд $p$ тоо буюу Валерагийн бодох бодлогын хэмжээ. Дараагийн $p$ мөрөнд бодлогуудыг бодох дарааллыг он цагийн эрэмбэтэйгээр дараах хэвтэйгээр хэвлэнэ: Валерагийн туслах оюутны индекс; Валера бодлогыг бодож эхлэх ёстой цагийн индекс; Валера бодлогыг бодож эхлэх ёстой цаг (түүний ажлын эхний минут); Валера бодлогыг бодож дуусах ёстой өдрийн дугаар; Валера бодлогыг бодож дуусгах цаг (түүний ажлын сүүлийн минут) байна. Гаралтын хэвийг сайн ойлгохыг хүсвэл жишээ тестүүдийг харна уу.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 3 4
calculus
algebra
history
58 23 15
00:00-08:15
08:20-08:35
09:30-10:25
19:00-19:45
calculus 1 09:36 100
english 4 21:15 5000
history 1 19:50 50
Гаралт
150
2
1 1 08:16 1 09:29
3 1 10:26 1 10:40
Оролт
2 2 1
matan
codeforces
1 2
00:00-08:00
09:00-09:00
12:00-12:00
18:00-18:00
codeforces 1 08:04 2
matan 1 08:02 1
Гаралт
3
2
2 1 08:01 1 08:01
1 1 08:02 1 08:03
Оролт
2 2 1
matan
codeforces
2 2
00:00-08:00
09:00-09:00
12:00-12:00
18:00-18:00
codeforces 1 08:04 2
matan 1 08:03 1
Гаралт
2
1
1 1 08:01 1 08:02
Сэтгэгдлүүдийг ачааллаж байна...