다리 건설

아주 오래전 2009년...

자이키노 마을에는 폭우가 자주 내린다. 비가 그친 뒤에는 보통 발로 건널 수 있는 두브롭카 강이 범람한다. 마을 사람들은 물에 잠긴 강을 건너려고 뜨는 다리를 만들고자 한다. 다행히 근처에 정착한 사업가가 목욕탕을 지었고, 그때 쓰고 남은 통나무가 있다.

남은 통나무는 모두 두께가 같다. 길이가 $a$인 통나무가 $x$개, 길이가 $b$인 통나무가 $y$개 있다.

다리는 $l$개의 행으로 이루어지며, 각 행은 하나 이상의 통나무로 구성된다. 안타깝게도 자이키노의 마지막 톱은 지난 범람 때 두브롭카에 빠져 사라졌으므로, 통나무를 잘라 조각낼 수 없다.

마을의 수석 기술자는 가능한 한 너비가 가장 넓은 다리를 만들려고 한다. 다리의 너비는 그 다리에 있는 행들 중 너비가 가장 좁은 행의 너비로 정해진다.

예를 들어 마을 사람들이 7행짜리 다리를 만들려고 하고, 길이 3인 통나무가 6개, 길이 2인 통나무가 10개 있다면 너비 5인 다리를 만들 수 있다.

입력에는 하나 이상의 테스트 케이스가 들어 있다. 각 테스트 케이스는 양의 정수 $x$, $a$, $y$, $b$, $l$ 다섯 개로 이루어진다. 이 값들은 모두 500을 넘지 않는다. 각 테스트 케이스에서 통나무의 총 개수는 적어도 $l$ 이상이다.

$d = \max(x, a, y, b, l)$이라 하자. 모든 테스트 케이스에 대한 $d$의 합은 5000 이하이다.

각 테스트 케이스마다 만들 수 있는 다리의 최대 너비를 한 줄에 정수 하나로 출력한다.