임금은 저울로 문서의 무게를 재고, 밤낮으로 처리할 분량을 정하여, 그 분량을 채우지 못하면 쉬지 못했다.
- 사마천, 『사기』 「진시황본기」
진시황은 자신이 정한 분량의 문서를 처리하기 전에는 쉬지 않았다고 한다. 당신은 그 곁에서 황제의 지시를 죽간에 받아 적는 사관이다. 황제가 쉬지 못한다는 말은 당신도 쉬지 못한다는 뜻이다.
황제는 지난 일 동안 자신이 내린 지시를 책으로 엮으라고 명했다. 죽간은 글을 적는 대나무 조각으로 여러 개를 순서대로 끈으로 엮어 한 권의 책을 만들 수 있다. 당신이 번째 날에 기록한 죽간은 개이다.
황제는 하루치 기록을 찾으려고 여러 권의 책을 펼치는 것을 몹시 싫어한다. 그렇다고 책이 쓸데없이 많아지는 것도 원하지 않아 완성한 책의 수를 권 이하로 제한했다. 황제의 심기를 헤아리는 일은 쉽지 않으므로 당신은 정해진 규칙대로 책을 엮기로 했다.
첫째 줄에 정수 과 이 공백으로 구분되어 주어진다.
둘째 줄에 정수 이 공백으로 구분되어 주어진다.
조건을 만족하는 가장 작은 용량 를 출력한다.
첫 번째 예제에서 용량을 으로 정하면 첫 번째 책에는 첫 번째와 두 번째 날의 죽간을 엮는다. 두 번째 책에는 세 번째 날의 죽간을 엮고 세 번째 책에는 네 번째와 다섯 번째 날의 죽간을 엮는다. 용량이 보다 작으면 하루치 죽간이 한 권에 들어가지 않거나 책이 권보다 많아진다.
두 번째 예제에서 용량을 으로 정하면 첫 번째 책에는 첫 번째와 두 번째 날의 죽간을 엮고 두 번째 책에는 세 번째 날의 죽간을 엮는다. 용량이 보다 작으면 한 권에 이틀의 죽간을 함께 엮을 수 없으므로 조건을 만족하지 못한다.
죽간은 첫 번째 날부터 마지막 날까지 기록된 순서대로 엮는다. 하루에 기록한 죽간을 여러 권의 책으로 나눌 수는 없지만 서로 다른 날의 죽간을 한 권에 함께 엮는 것은 가능하다. 날을 구분하기 위해 빈 죽간을 넣지는 않는다.
당신은 모든 책의 용량을 같은 양의 정수 로 정해야 한다. 한 권의 책에는 최대 개의 죽간을 엮을 수 있으며 하루치 죽간이 한 권에 들어갈 수 있어야 한다. 책이 너무 무거워지지 않도록 용량은 가능한 한 작게 정하려고 한다.
처음에는 첫 번째 책에 넣을 죽간이 없다. 그날의 죽간을 모두 추가했을 때 죽간의 개수가 이하라면 현재 책에 이어서 엮는다. 를 초과한다면 현재 책에는 더 이상 죽간을 추가하지 않고 다음 책에 그날의 죽간을 모두 엮는다. 죽간의 개수가 정확히 가 되는 경우에는 현재 책에 엮는다.
당신이 모든 죽간을 엮었을 때 완성한 책이 권 이하가 되도록 하는 가장 작은 용량 를 구하여라.
