Egy viharos este a szél letépte János gazda istállóinak tetejét és kapuit. Szerencsére a tehenek egy része máshol tartózkodott, ezért az istálló nem volt teljesen tele. A tehenek egy-egy külön karámban töltik az estét, a karámok egy hosszú sorban egymás mellett helyezkednek el. Néhányban van tehén, néhányban nincs. Minden karám szélessége azonos. János gazda a vihar után gyorsan megpróbálja bedeszkázni a karámokat, mert az ajtókat letépte a szél. E célból tetszőleges hosszúságú deszkákat tud rendelni, de csak néhány darabot. János szeretné elérni, hogy a megrendelt deszkák hosszának összege minimális legyen. Adott M (1 <= M <= 50), a rendelhető deszkák darabszámának maximuma; S (1 <= S <= 200), a karámok száma; C (1 <= C <= S) a tehenek száma; és a C foglalt karám sorszáma (1 <= sorszám <= S).
Feladat
Írjunk programot, ami megadja, hogy legkevesebb hány karám bedeszkázásával lehet kordában tartani a teheneket.
Bemenet
A bemenet első sora M, S és C értékét adja meg. Ezután C sorban egy-egy foglalt karám sorszáma következik.
Kimenet
A bedeszkázott karámok száma.
Példa
Bemenet |
Kimenet |
4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43
|
25
|
Például: 3-8, 14-21, 25-31 és 40-43.
Tesztadatok
Címkék
A feladat forrása: USACO training material, Barn Repair
Algoritmusok:
megoldás |