在情人節這天，萬人迷先生決定買 N 朵玫瑰花送給他的女性朋友們。
不過這年頭的玫瑰花都是一盒一盒在賣的。
村子裡面有兩個專賣玫瑰花的攤販，第一攤可以每次花 A 塊錢購買 B 朵玫瑰花。第二攤可以每次花 C 塊錢購買 D 朵玫瑰花。
請問萬先生想買至少 N 朵玫瑰花的話，至少要花多少錢？
一個輸入檔包含多筆測試資料，第一行包含測資筆數 T (T<=100)。
對於每筆測試資料包含五個正整數 N, A, B, C, D。
至少有 20% 的分數滿足：所有數字 <= 1000。
至少有 60% 的分數滿足：N, A, B, C, D <= 105
至少有 80% 的分數滿足：N, A, B, C, D <= 109
至少有 80% 的分數滿足：N <= 1015，A, B, C, D <= 105。而且答案保證不超過 1018。
對於每一筆測試資料，請輸出萬先生要花的最低金額。
2 5 4 1 6 3 22 3 2 14 10
12 31
Migrated from old NTUJ.
BOI2012 Day0
| No. | Testdata Range | Score |
|---|