좀비의 보물 상자

용감한 전사들이 버려진 마을에 도착해 산더미 같은 보물과 커다란 보물 상자를 발견했지만, 성난 좀비들도 함께 있었습니다.

전사들은 좀비를 물리치고 보물을 모두 가져가기로 마음먹습니다. 하지만 아침부터 밤까지 이어진 치열한 전투 끝에, 좀비들은 죽지 않는 불사의 존재라는 사실이 드러납니다.

그래도 보물을 이대로 둘 수는 없습니다. 문제는 보물 상자의 용량에 한계가 있어 모든 보물을 담을 수 없다는 점입니다. 보물은 두 종류뿐입니다: 에메랄드와 사파이어. 모든 에메랄드는 크기와 가치가 서로 같고 수량은 무한하며, 사파이어도 마찬가지입니다.

상자의 용량 $N$, 그리고 각 보석의 크기와 가치가 주어질 때, 전사들이 상자에 담아 가져갈 수 있는 보물의 최대 총 가치를 구하세요. 즉, $x \cdot S_1 + y \cdot S_2 \le N$ 을 만족하는 음이 아닌 정수 $x, y$ 에 대해 $x \cdot V_1 + y \cdot V_2$ 를 최대화하면 됩니다.

첫 줄에 테스트 케이스의 개수 $T$ ($T \le 200$)가 주어집니다.

각 테스트 케이스는 한 줄에 다섯 개의 정수 $N, S_1, V_1, S_2, V_2$ 로 이루어집니다. $N$ 은 보물 상자의 용량, $S_1$ 과 $V_1$ 은 에메랄드 하나의 크기와 가치, $S_2$ 와 $V_2$ 는 사파이어 하나의 크기와 가치입니다. 모든 정수는 양수이며 32비트 부호 있는 정수 범위 안에 들어갑니다.

각 테스트 케이스마다 한 줄에 케이스 번호와 상자에 담아 가져갈 수 있는 보물의 최대 총 가치를 출력하세요. 형식은 Case #k: 값 이며, 여기서 $k$ 는 1부터 시작하는 테스트 케이스 번호입니다.