루미 알고리즘

#1358골드Vandrarhem

PO 2015 결선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Arash ska anordna en onsitefinal för PO, Potatisskalarolympiaden. Det kommer att komma N deltagare och Arash ska nu boka boende för de tävlande. Arash har siktat in sig på ett närliggande vandrarhem för att boka bäddplatserna som behövs.

Det finns M typer av bäddar. För en given bäddtyp i så kostar en bädd c_i kronor och det finns b_i tillgängliga bäddar av den typen. Vandrarhemmet har inga nuvarande bokningar, så det är fritt fram att boka så mycket som behövs.

Den svenska potatisskalarolympiaden är inte så duktiga på matematik, och behöver nu din hjälp. De vill veta den minimala möjliga kostnaden för att boka de bäddar som behövs på vandrarhemmet. Kan du hjälpa dem?

Indata

Första raden består av två heltal, antalet deltagare N (1 ≤ N ≤ 100) samt antalet bäddtyper M (1 ≤ M ≤ 5). Sedan följer M rader, vardera med talen c_i (100 ≤ c_i ≤ 1000) och b_i (1 ≤ b_i ≤ 100) som beskrivet ovan.

Det kommer alltid finnas bäddar så det räcker för alla deltagare.

Utdata

Skriv ut ett heltal på en rad: den minsta möjliga kostnaden för den svenska Potatisskalarolympiaden att hyra på vandrarhemmet för en natt.

Förklaring av exempel

Låt oss förklara det första indataexemplet. Du köper slut på de 8 billigaste bäddarna för en total kostnad på 2400, sedan köper du två av de lite dyrare bäddarna för en total kostnad på 1000. Slutpriset blir 3400.

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.

GruppPoängvärdeGränser
11001 ≤ N ≤ 100, 1 ≤ M ≤ 5, 100 ≤ c_i ≤ 1000, 1 ≤ b_i ≤ 100

예제

예제 1

입력
10 2
500 30
300 8
출력
3400

예제 2

입력
10 3
150 5
200 3
100 3
출력
1450

출처 표기

출처: Programmeringsolympiaden 2015년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.