ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / USACO /

Уралдаанд хүүхдүүд өндөр оноо авах тусам USACO-гийн хамт олон бид баяртай байдаг билээ. Бид уралдаанаа оролцогчид аль болох олон оноо авах байдлаар зохион байгуулахыг хичээдэг бөгөөд чиний туслалцааг хүсч байна.

Бид бодлогоо хэд хэдэн ангилал болгон хуваасан бөгөөд “ангилал” гэдэг нь хязгааргүй тооны бодолтын хугацаа нь ижил, зөв бодолт хийсэн тохиолдолд ижил оноо авахаар бодлогуудаас бүтнэ. Чиний даалгавар бол USACO-гийн ажилтанд

• уралдаанд сонгосон бодлогуудын нийлбэр оноо нь хамгийн их байхаар гэхдээ
• нийт бодолтын хугацаа нь уралдааны хугацаанд багтаж байхаар

ангилал бүрээс хэдэн бодлого оруулбал зохилтойг хэлэх програм бичих.

Оролтонд уралдааны үргэлжлэх хугацаа M (1 <= M <= 10,000), бодлогын ангиллын тоо N (1 <= N <= 10,000) өгөгдөнө.

Түүний дараагийн N мөрийн мөр бүрт тухайн ангиллыг илэрхийлэх 2 бүхэл тоо байна. Үүнд эхний бүхэл тоо нь тухайн ангиллын бодлогын оноо (1 <= оноо <= 10000), хоёр дахь бүхэл тоо нь тухайн ангиллын бодлогыг бодоход хэдэн минут  (1 <= минут <= 10000) зарцуулахыг илэрхийлнэ.

Чиний програм уралдааныг хамгийн өндөр оноотой байлгахын тулд ангиллал бүрээс хэдэн бодлого сонгохыг тогтоох ёстой. Ангилал бүрээс сонгох бодлогын тоо нь сөрөг биш бүхэл тоо байна (0, 1 эсвэл их). Боломжит хамгийн их оноог ол.

Програмын Нэр: inflate

Оролтын Формат

Жишээ Оролт (файл inflate.in)

300 4

100 60

250 120

120 100

35 20

Гаралтын Формат

Хамгийн өндөр оноо.

Жишээ Гаралт (файл inflate.out)

605

(#2-с хоёр бодлого #4-с гурван бодлого.)

Орчуулсан : Б.Даваабаяр