| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 236 | 71 | 58 | 32.584% |
영인이와 $N-1$명의 친구들은 학식을 먹으려고 한다. 학식은 $M$개의 메뉴로 구성되어 있으며, 메뉴들은 1ドル$번부터 $M$번까지 번호가 매겨져 있다. $i$번 메뉴는 가격이 $A_i$이고 수량이 $B_i$이다.
영인이와 친구들은 메뉴의 수량을 초과하지 않도록 조심스럽게 메뉴를 선택했다. 모든 사람은 한 개의 메뉴만 선택할 수 있으며, 메뉴를 선택하지 않는 경우는 없다.
영인이는 메뉴 구성에 따라 본인의 불만도가 달라진다. 선택된 $N$개의 메뉴의 번호를 $x_1,x_2,\cdots ,x_N$이라 할 때, 불만도는 다음과 같이 정의된다.
불만도 \( =\left( \sum_{i=1}^{N}A_{x_i} \right)\times\lvert \{x_1,x_2,\cdots ,x_N\} \rvert\)
여기서 $\sum_{i=1}^{N}A_{x_i}$는 선택된 메뉴들의 가격의 합이며, $\lvert \{x_1,x_2,\cdots ,x_N\} \rvert$는 선택된 메뉴의 종류 수를 나타낸다.
가능한 불만도의 최솟값을 출력하시오.
첫 번째 줄에 사람의 수 $N$과 메뉴의 수 $M$이 공백으로 구분되어 주어진다. $( 1\leq N\leq 1,円 000;$ 1ドル\leq M\leq 100 )$
다음 $M$개의 줄에 걸쳐, $i$번째 줄에 $i$번 메뉴의 가격 $A_i$와 수량 $B_i$가 공백으로 구분되어 주어진다. $(1\leq A_i,B_i\leq 10^9;$ $\sum_{i=1}^{M}{B_i}\geq N)$
입력으로 주어지는 모든 수는 정수이다.
가능한 불만도의 최솟값을 출력하시오.
3 3 3000 2 2000 1 5000 3
15000