민성이는 도시를 운영하는 게임을 즐겨한다.

게임은 자원을 C만큼 가지고 시작하며, 자원을 사용해서 도시에 생산 시설을 건설할 수 있다.

생산시설은 모두 N종류가 있으며, 이들은 각각 A_i일차 일때만 설치할 수 있다는 제약이 있다.

설치할 때는 B_i의 비용이 들고, 생산시설을 철거한다면 C_i의 자원을 돌려받을 수 있다.

설치된 생산시설은 설치된 날의 다음날부터 철거되기 전날까지 매일 D_i의 자원을 생산한다.

게임의 온갖 컨텐츠를 섭렵해버린 민성이는 지금 모든 도전과제 클리어를 목표로 하고 있다.

민성이가 노리고 있는 도전과제 “두 개는 필요 없어”는 K일차까지 생산시설을 한 번에 2개 이상 가지지 않고 게임을 진행해야 클리어할 수 있다!

즉, 다른 생산시설을 설치하려면 기존의 생산시설을 철거해야 한다. 다행스럽게도 기존의 시설을 철거한 날 바로 다른 시설을 설치할 수 있다.

민성이는 K일이 모두 지나가면 가진 생산시설을 철거할 생각이고, 한 번에 하나의 생산시설만 가지고 최대한의 자원을 얻으려고 한다. (도전과제가 목표이므로 자원을 다른 곳에 사용하지는 않는다.)

알고리즘 전문가인 여러분들이 민성이를 도와주자!

도시 운영 게임 timer 2s memory 128MB

도시 운영 게임 2s 128MB