Lista de probleme 1

Vrăjitorul Arpsod este deranjat la culme de câinii vecinului. Aceștia au prostul obicei de a veni să-și îngroape oasele în curtea vrăjitorului. Înainte de a lua măsuri drastice împotriva vecinului, Arpsod a decis să construiască un gard despărțitor între cele două curți. Gardul poate fi privit ca un segment de dreaptă de lungime N metri. Astfel, Arpsod a angajat K meseriași pentru a-i construi gardul. Fiind un tărâm cât se poate de democratic, fiecare muncitor a decis că el este dispus să construiască doar o parte din gard pornind de la al x-lea metru și pană la al y-lea metru inclusiv. Fiecare meseriaș cere o anumită sumă de bani pentru lucrarea sa.

Arpsod poate decide să angajeze o parte dintre muncitori, pentru a realiza întregul gard. Dacă doi muncitori angajați au de construit o porțiune comună a gardului, ea va fi lucrată de amândoi, dar fiecare își va primi integral suma solicitată.

Ajutați-l pe Arpsod să-și aleagă meseriașii astfel încât gardul să fie construit integral și el să plătească o sumă minimă de bani.