Програмчлал, Алгоритмд дуртай бүхэнд зориулав

Та Египтийг дорнодоос өмнөд уруу шулуунаар дайран гарах тэмцээнд оролцож байна. Эхлээд хамгийн дорнод зүгийн цэгээс эхлэх ба дүрэм ёсоор шулууны дагуу өмнөд уруу явах ёстой.

Шулууны дагуу нийт N тээвэрлэгч байх ба зүх тээвэрлэгчид эхлэл төгсгөлийн цэг байх ба аль нэг цэгт нь очиход нөгөө цэг уруу агшин зөөж өгдөг. Бүх тээвэрлэгчидийн эхлэл төгсгөл нь шулууны дагуу байрлах ба давхцахгүй. Та дорнодоос өмнөд уруу явахдаа  замд тааралдах ямарч тээвэрлэгчийг заавал ашиглах ёстой.

Ямарваа нэгэн тээвэрлэгчийг ашиглахад таньд 1 оноо нэмэгдэнэ.  Тэмцээний зорилго бол аль болох олон оноо авах. Илүү оноо авахын тулд та шулууны дагуу дахин M тээвэрлэгч тавьж болох ба бүх тээвэрлэгчийн эхлэл төгсгөл давхцаж болохгүй ба энэ нь ямар ч тохиолдолд тэмцээнийг дуусгах хангалттай нөхцөл болно.

Оролт

Эхний мөр N // 1< = N < = 1,000,000

Дараагын мөр  M // 1 < = M < = 1,000,000

x+2-р мөрөнд х-р тээвэрлэгчийн эхлэл төгсгөлийн цэг Wx, Ex

// 1 < = x < = N; 1 < = Wx < Ex < = 2,000,000

Гаралт

Таны авч чадах хамгийн их оноо

Жишээ оролт

3

1

10 11

1 4

2 3

Жишээ гаралт

6

Энэ жишээнд хэрвээ шууд явах бол эхлээд 2-р тээвэрлэгчийг ашиглаад түүний дараа 1-р тээвэрлэгчийг ашиглан барианд орно. Авах оноо 2.

Хэрэв 0.5, 1.5 дээр эхлэл төгсгөлтэй 1 тээвэрлэгч (4-р тээвэрлэгч) нэмж тавъя.

Тэгвэл эхлээд 4-р тээвэрлэгчээс эхлээд 3, 2, 4, 2 ,1 гэсэн дарааллаар тээвэрлэгчийг ашиглаад  нийт 6 оноо авах боломжтой.