베스트 피자(Best Pizza) timer 1000초 memory 64MB

올해도 꿀꿀이 올림피아드 대회가 열린다. 대회를 위한 예비 심사에서 많은 꿀꿀이들이 무난히 심사를 통과했지만 앙데용꿀꿀이는 예비심사를 통과하지 못했다. 이유는 꿀꿀이라고 하기에는 너무 날씬했기 때문이다.

예비심사에서 떨어진 앙데용꿀꿀이는 10일 후에 있을 추가 심사에는 꼭 통과하기로 결심하고 살을 찌울 계획을 세웠다. 하지만 그 짧은 시간에 필요한 만큼의 살을 찌우려면 '비게로만'이나 '살로우만' 같은 최고의 트레이너를 고용해야 해서 너무 많은 비용이 필요하였다. 

너무 속상하여 엉엉 울고 있었는데 마침 그 옆을 지나가던 엉뚱꿀꿀이 송뒤뚱이 자초지종을 물었다. 

사정을 듣고 난 송뒤뚱은 '이거 비밀인데 1번가 APM(Ace Pig Master)피자집에가서 베스트 피자를 먹어 보는건 어떨까? '하고는 뒤뚱거리며 갈길을 갔다. 

APM피자에서는 도우는 한 종류이지만  가격이 모두 같은 토핑이 N종류 있다. N개의 토핑 중 0개이상 N개 이하의 토핑을 중복 없이 선택하여 피자를 주문할 수 있다.

따라서 여러 종류의 맞춤형 피자가 만들어지는데 이 피자들 중 1달러 당 칼로리가 가장 높을 때 이 피자를 베스트 피자라고 한다.

도우의 칼로리는 C이며, 각 i번째 토핑의 칼로리는 D_i로 정해져있다.

피자의 가격은 도우의 가격이 A달러이고, 고른 토핑의 개수가 K개, 토핑 당 가격이 B달러라고 하면 A + K \times B 달러이다.

시간과 돈을 모두 절약해야 하는 앙데용꿀꿀이 입장에서는 베스트 피자를 주문해 먹을 작정이다. 앙데용꿀꿀이를 도와 베스트피자를 만들어보자.