화학 제품

상근이는 서로 다른 병에 담긴 세 가지 화학 물질 A, B, C를 가지고 있다. 서로 다른 두 화학 물질을 같은 양만큼 혼합하면 화학 제품 하나를 만들 수 있다.

• A와 B를 혼합하면 AB가 된다.
• B와 C를 혼합하면 BC가 된다.
• C와 A를 혼합하면 CA가 된다.

물질 하나와 다른 물질 하나를 혼합하면 제품 하나를 얻는다. AB, BC, CA의 단위 가격은 서로 다를 수 있으므로, 어떤 제품을 만드느냐에 따라 이익이 달라진다. 혼합은 항상 정수 단위로만 할 수 있다.

예를 들어 A가 5, B가 3, C가 7만큼 있고 단위 가격이 아래와 같다고 하자.

A 1과 B 1을 혼합해 AB 1을 만들면 $100을 얻는다. 이어서 B 2와 C 2를 혼합하면 $60을, C 4와 A 4를 혼합하면 $320을 얻는다. 총 이익은 $480이며, 이것이 얻을 수 있는 최대 이익이다. 어떤 물질은 남겨 두어도 된다. 이 예에서는 C 하나를 사용하지 않았다.

다른 예로 A, B, C가 각각 3만큼 있고 AB, BC, CA의 가격이 모두 $100이라고 하자. A 2와 B 2를 혼합해 $200을, B 1과 C 1을 혼합해 $100을, C 1과 A 1을 혼합해 $100을 얻으면 총 이익은 $400이 되고, 이것이 최대 이익이다.

상근이가 가진 A, B, C의 양과 AB, BC, CA의 단위 가격이 주어질 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 A, B, C의 양이, 둘째 줄에는 AB, BC, CA의 단위 가격이 공백으로 구분되어 주어진다. 입력으로 주어지는 모든 수는 정수이며 $1$ 이상 $1{,}000$ 이하이다.

각 테스트 케이스마다 얻을 수 있는 최대 이익을 한 줄에 하나씩 출력한다.