마법 구슬 찾기

당신은 모양과 질량이 완전히 동일한 $k+1$ 개의 구슬을 갖고 있다. 이 중 $k$ 개의 구슬은 일반적인 구슬이고, 1개는 마법 구슬이다. 당신은 마법 구슬을 찾아 마법의 성에 들어가려고 한다.

마법 구슬과 일반 구슬을 육안으로 구별할 수 있는 방법은 없지만, 마법 구슬을 찾아내는 데에 사용할 수 있는 $M$ ( $M \ge 2$ )개의 주머니가 있다. 주머니에는 $0$ 부터 $M-1$ 까지의 번호가 붙어 있다.

주머니를 활용하여 마법 구슬을 찾을 수 있는 방법은 아래와 같다.

갖고 있는 모든 구슬을 $M$ 개의 주머니에 나눠 담는다.
- 어떤 주머니에도 넣지 않은 구슬이 있으면 안 된다.
- 구슬을 담지 않은 빈 주머니는 있어도 된다.
- 주머니 속에는 구슬만 담을 수 있으며, 다른 주머니를 담을 수는 없다.
주문을 외운다.
주문을 외운 직후:
- 마법 구슬이 들어 있지 않은 주머니 속의 구슬들은 모두 소멸된다.
- 마법 구슬이 들어 있는 주머니 속의 구슬들은 마법 구슬의 보호를 받아서 소멸되지 않는다. 하지만, 주문으로 인한 부수 효과를 수습해야 하고, 이 과정에서 비용이 든다. 마법 구슬이 $i$ 번 주머니에 들어 있었고, $i$ 번 주머니에 구슬 $j$ 개가 들어 있었다면, $A\[i] \times j + B\[i]$ 원 ( $A\[i] \ge 0$ , $B\[i] \ge 1$ )이 든다.

마법 구슬은 절대로 소멸되지 않으므로, 위의 과정을 마법 구슬 1개만 남을 때까지 반복하면 마법 구슬을 찾을 수 있다.

당신은 구슬들을 주머니에 나눠 담는 전략을 수립하여, 최악의 경우에 마법 구슬을 찾는 데에 드는 비용을 최소화하고자 한다. 즉, $k+1$ 개의 구슬 중 어떤 구슬이 마법 구슬이더라도 총 $w$ 원 이하를 들여 마법 구슬을 찾을 수 있는 최소한의 $w$ 를 찾고자 한다.

$0$ 이상 $N-1$ 이하의 모든 $k$ 에 대해 이 문제를 해결하는 함수를 작성하라.

마법 구슬 찾기

문제

제한