시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 466 155 121 36.228%

문제

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

A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다.

예를 들어, A를 5만큼, B를 3만큼, C를 7만큼 가지고 있고, 각 화학 제품의 가격은 다음과 같은 경우를 생각해보자.

화학 제품 단위 가격
AB $100
BC $30
CA $80

A 하나와 B하나를 혼합해 AB 하나를 만들면 $100을 얻게 된다. 그 다음 B 2개와 C 2개를 혼합하면 $60을 얻게 되고, C 4개와 A 4개를 혼합해 $320을 얻게 된다. 총 이익은 $480이 되고 이 이익이 가능한 이익 중 최대값이다. 한 화학 물질은 모두 사용하지 않을 수도 있다. 이 예제에서는 C를 하나 사용하지 않았다.

다른 예로, A가 3개, B가 3개, 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보다 작거나 같다.

출력

각 테스트 케이스 마다 최대 이익을 출력한다.

예제 입력

2
5 3 7
100 30 80
3 3 3
100 100 100

예제 출력

480
400

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: koyh1200