스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Som bekant går björnar i ide under vintern. Men vid ekvatorn blir det inte mörkt och kallt under vintern, så sedan en björnfamilj för många år sedan flyttade söderut har björnarna i björnsamhället som uppstått börjat gå i ide vid helt olika tidpunkter under året. Björne har öppnat ett magasin och är orolig för tjuvar under den del av året då han själv sover. Han ska därför anställa andra björnar så att det alltid är någon av de anställda som är vaken och kan vakta magasinet.
Totalt är det N björnar som sökt jobbet. Varje björn går i ide någon viss dag på året för att sova exakt d dagar i sträck, och kan inte jobba under någon av dessa dagar. Hur många björnar behöver Björne som minst anställa, givet att Björne kommer vakta sitt magasin själv när han är vaken?
Räkna med att varje år har 365 dagar (björnar som bor vid ekvatorn bryr sig inte om skottår), och att:
- januari har 31 dagar,
- februari har 28 dagar,
- mars har 31 dagar,
- april har 30 dagar,
- maj har 31 dagar,
- juni har 30 dagar,
- juli har 31 dagar,
- augusti har 31 dagar,
- september har 30 dagar,
- oktober har 31 dagar,
- november har 30 dagar och
- december har 31 dagar.
Indata
Första raden innehåller två heltal N och d (2 ≤ N ≤ 10^5, 1 ≤ d ≤ 364), antalet björnar (inklusive Björne), samt antalet dagar varje björn sover.
De följande N raderna innehåller dagarna då respektive björn går i ide. De anges på formen dd/mm.
Första björnen som anges är Björne själv.
Utdata
Skriv ut en rad med ett heltal, det minsta antalet björnar som Björne måste anställa.
Om det inte går att vakta magasinet alla dagar, skriv ut -1.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
| Grupp | Poängvärde | Gränser |
| 1 | 30 | N ≤ 15 |
| 2 | 40 | d ≤ 182 |
| 3 | 30 | Inga ytterligare begränsningar. |
예제
예제 1
5 31 01/01 15/12 03/07 06/11 17/09
1
예제 2
12 303 01/01 01/02 01/03 01/04 01/05 01/06 01/07 01/08 01/09 01/10 01/11 01/12
5
예제 3
6 100 17/05 05/07 13/04 29/06 02/05 29/04
-1