O companie feroviară a lansat recent un nou prototip de tren, format dintr-un singur vagon cu N scaune. Scaunele sunt numerotate la 1 la N (numerotarea începe de la partea din față a trenului) și sunt aranjate într-o linie, unul în spatele altuia. Următoarele reguli urmează să fie respectate de fiecare pasager:

1. Pasagerii vor urca în tren doar pe ușa din spate, care este situată după toate scaunele. Odată urcați, pasagerii au dreptul să se deplaseze doar spre partea din față și pot părăsi trenul doar prin ușa din față (care este situată în fața tuturor scaunelor).
2. Fiecare pasager va ocupa locul situat imediat după ultimul scaun ocupat. Dacă trenul este absolut liber, pasagerul va ocupa scaunul din față (marcat ca locul 1).
3. Nici un pasager nu are dreptul să-și părăsească locul până la debarcare.
4. La fiecare stație, pasagerii care au ajuns la destinație părăsesc trenul. Dacă există pasageri pe scaune în fața celui care a ajuns la destinație, ei de asemenea vor părăsi trenul, chiar dacă încă nu au ajuns la destinația lor.
5. Odată ce a ieșit din tren, pasagerul nu mai are dreptul să urce înapoi.

Ruta trenului are M stații, numerotate de la 1 la M. Trenul se oprește în fiecare stație, începând cu stația 1 și terminând cu stația M. La toate cele M stații de tren se află în total N pasageri, numerotați de la 1 la N. Pentru fiecare pasager se cunoaște din timp prețul tichetului, stația de îmbarcare și stația de debarcare. Compania feroviară dorește să aibă doar clienți fericiți, care ajung la destinația lor. Pentru a avea doar clienți fericiți, compania a permis conductorului să selecteze pasagerii care se pot îmbarca, precum și ordinea în care li se permite îmbarcarea. Astfel, conductorul poate să decidă să nu permită unor pasageri să urce în tren. Determinați profitul maximal care poate fi obținut de companie având doar clienți fericiți, precum și o ordine de îmbarcare validă, care permite obținerea acestui profit.