31416번 - 가상 검증 기술

문제

현대오토에버의 가상 검증 기술은 차량·시스템·제어기를 가상화하고 가상 주행 환경, 검증 도구 등을 제공해 기능별 검증, 기능 간 연계 검증, 시스템 단위 검증을 하드웨어 없이 가상으로 진행할 수 있도록 하는 기술이다. 가상 검증은 조기 검증을 통한 품질 확보와 실제 검증이 불가한 악조건 검증 시뮬레이션을 가능하게 한다. 또한 차량의 컴퓨팅 복잡도가 상승하는 SDV 시대에 가상 검증 기술은 다른 차원의 잠재적 SW 품질 리스크를 고려하여 차량의 안정성과 성능을 확보할 수 있는 효과적인 검증 방법이다.

현대오토에버의 숙련 연구원인 도훈이와 신입 연구원인 상혁이는 차종 $A$와 $B$의 가상 검증 업무를 담당하고 있다. 두 차종 $A$와 $B$에 대해 가상 검증 시뮬레이션을 1ドル$회 수행하는 데 각각 $T_A, T_B$의 시간이 소요된다. 또한 품질 확보를 위해 차종 $A$와 $B$에 대해 테스트가 필요한 가상 검증 항목은 각각 $V_A, V_B$개이며, 한 번의 가상 검증 시뮬레이션으로 하나의 가상 검증 항목을 테스트할 수 있다.

도훈이와 상혁이는 각자 수행할 시뮬레이션 항목을 잘 분배하여 가상 검증을 수행하고자 한다. 숙련 연구원인 도훈이는 차종 $A, B$의 가상 검증을 수행할 수 있지만, 신입 연구원인 상혁이는 차종 $A$의 가상 검증만 수행할 수 있다. 도훈이와 상혁이는 한 번에 하나의 가상 검증 시뮬레이션을 수행할 수 있으며, 두 명이서 같은 가상 검증 항목을 시뮬레이션할 수 없고, 가상 검증 시뮬레이션을 수행한 뒤 다음 시뮬레이션을 준비하는 데 소요되는 시간은 없다고 가정한다. 또한 가상 검증 시뮬레이션은 수행 도중 중단할 수 없다.

두 차종의 가상 검증 시뮬레이션을 모두 마쳤을 때 업무를 완료할 수 있다. 도훈이와 상혁이가 가상 검증 업무를 완료하는 데 소요되는 시간의 최솟값을 구해보자.

입력

첫 번째 줄에 테스트 케이스의 수 $Q$가 주어진다. $(1 \leq Q \leq 1,円 000)$

두 번째 줄부터 각 테스트 케이스마다 한 줄에 차종 $A,ドル $B$의 가상 검증 시뮬레이션을 1ドル$회 수행하는 데 걸리는 시간 $T_A, T_B$와 가상 검증 시뮬레이션을 수행해야 하는 항목의 수$ V_A, V_B$가 공백으로 구분되어 주어진다. $(1\leq T_A, T_B, V_A, V_B\leq 100)$

출력

각 테스트 케이스마다 한 줄에 하나씩 가상 검증 업무를 완료하는 데 걸리는 시간의 최솟값을 출력한다.

제한

힌트