문제

카카오에는 뛰어난 개발자들을 위한 다양한 행사들이 있는데, 그 중 하나가 24K라고 하는 사내 해커톤 행사이다. 이 행사에서 카카오 크류들은 잉여력을 폭발시켜 기발한 제품들을 만들어낼 수 있다. 24K가 크류들의 가슴을 뛰게하는 또 다른 이유는 바로 제공되는 어마어마한 상품들이다. 행사의 진행을 맡은 Patrick은 크류들이 24시간동안 여러가지 게임들을 즐기면서 많은 상품을 가져갈 수 있도록 계획을 세웠다. 그 중 하나가 무지무지라는 게임이다. 게임의 방법은 다음과 같다.

총 N (1 \le N \le 30)$N (1 \le N \le 30)$ 종류의 무지(MUZI) 인형이 있다. 편의상 이 인형들을 1$1$번부터 N $N$번 인형이라고 구분하자. 이 중 오직 1$1$번 인형만 사내 스토어에서 A (1 \le A \le 1000)$A (1 \le A \le 1000)$원에 구매할 수 있다. i (1 \le i < N)$i (1 \le i < N)$번 인형은 i+1$i+1$번 인형으로 바꿀 수 있는데, 이는 위험과 비용을 감수해야 하는 일이다. 번호가 클 수록 인형이 엄청 귀여워지기 때문이다. 위험을 감수하겠다고 결정을 했으면 우선 c_i (1 \le c_i \le 100)$c_i (1 \le c_i \le 100)$원을 지불하고, i$i$번 인형을 Patrick에게 맡겨야 한다.

Patrick은 인형의 운명을 다음과 같이 결정한다.

• s_i (1 \le s_i < 100)$s_i (1 \le s_i < 100)$% 성공 확률로 i + 1$i + 1$번 인형으로 교환해준다.
• 실패한다면
  • d_i (0 \le d_i \le 100)$d_i (0 \le d_i \le 100)$ 확률로 인형을 어린이 병원에 기부한다.
  • 기부하지 않는다면
    • b_i = 0$b_i = 0$일 경우 i$i$번 인형을 돌려준다.
    • b_i = 1$b_i = 1$일 경우 i - 1$i - 1$번 인형을 돌려준다. (b_1$b_1$은 항상 0$0$이다.)

인형을 기부하고 나면 이 게임에 참가하기위해 다시 1$1$번 인형을 A$A$원에 구매해야만 한다.

게임의 설계를 마친 Patrick은 똑똑한 크류에게 게임을 조금 더 유리하게 만들어주기로 결심했다. 각각의 크류는 게임을 DA 모드와 UM 모드 중 하나로 즐길 수 있다. (단, 한 번 정하면 바꿀 수 없다.)

• DA 모드: 각각의 성공률 s_i$s_i$가 K (1 \le K \le 100)$K (1 \le K \le 100)$%만큼 증가한다. 예를 들어, s_i$s_i$가 50%이고, K가 10이라면 성공률은 10% 증가한 55%가 된다. 절대적으로 증가하는 것이 아니라 상대적으로 증가함에 유의하자. 물론 성공율이 100%를 넘으면 무조건 성공한다.
• UM 모드: S (1 \le S \le 3)$S (1 \le S \le 3)$번 연속 번호가 낮은 인형으로 교환받을 때, 그 바로 다음 시도는 성공율을 100%로 보장해준다. 이 때, 성공율이 100%여도 비용은 동일하게 지불해야한다. 예를 들어, S$S$ = 2 라고 하자. 5번 인형을 Patrick에게 맡겼는데 4번 인형을 돌려주었고, 이 4번 인형을 다시 맡겼을 때 3번 인형을 돌려주었다면 이 3번 인형을 다시 Patrick에게 맡겼을 때, 무조건 4번 인형으로 돌려준다. 비용은 인형을 맡길 때 마다 모두 정상적으로 지불해야 한다. 기부를 해서 1번 인형을 다시 구매해야하는 경우는 더 낮은 인형을 돌려받은 것으로 고려하지 않는다. 또한 같은 번호의 인형을 돌려받은 경우도 해당되지 않는다.

게임의 황제 Chloe는 꼭 i (1 < i \le N)$i (1 < i \le N)$번 인형을 갖고 싶다. 집요한 승부사인 Chloe는 i$i$번 인형을 얻을 때 까지 무한히 게임을 반복할 예정이다. (인형은 Patrick이 무수히 많이 준비해 두었으니 걱정하지 않아도 된다.) 이 경우 Chloe는 DA 모드로 게임을 해야할까 UM 모드로 게임을 해야할까?