Joys of Trading timer 1s memory 1024MB

아폴랑카와 비들스도르프는 최근 연락을 취한 두 작은 신석기 시대 마을입니다. 리소스는 1부터 N까지 번호가 매겨진 N개의 자원이 있으며, 각 마을은 독립적으로 그 중 어떤 것이든 생산할 수 있지만 서로 다른 효율성을 가지고 있습니다. 자원 i를 한 단위 생산하기 위해 아폴랑카는 A_i 시간이 필요하고, 비들스도르프는 B_i 시간이 필요합니다. 현재 아폴랑카는 각 주어진 시간 당 U_i 단위의 자원을 생산하고, 비들스도르프는 W_i 단위를 생산합니다.

각 마을은 현재 최대 용량으로 작동 중이며, 현재 사용 중인 인간-시간을 더 할당할 수 있는 방법이 없습니다. 그러나 최근에 발견된 무역의 이점으로 두 마을은 모든 필요한 리소스를 생산하면서 총 인간-시간을 줄일 수 있으며, 그 결과 여가 시간을 보내고 게임을 즐길 수 있습니다. 마을이 협력하여 작업을 조정하고 서로 리소스를 교환하기만 하면 됩니다.

예를 들어, N = 2인 경우 리소스 1은 나무이고 리소스 2는 음식입니다. A_1 = 1, U_1 = 2, B_1 = 4, W_1 = 1, A_2 = 2, U_2 = 1, B_2 = 3 및 W_2 = 4라고 가정합니다. 그러면 아폴랑카는 4 인간-시간의 작업을 수행합니다. U_1 = 2 단위의 나무를 생산하기 위해 A_1 U_1 = 2를 사용하고, U_2 = 1 단위의 음식을 생산하기 위해 A_2 U_2 = 2를 사용합니다. 마찬가지로, 비들스도르프는 16 인간-시간의 작업을 수행합니다. W_1 = 1 단위의 나무를 생산하기 위해 B_1 W_1 = 4를 사용하고, W_2 = 4 단위의 음식을 생산하기 위해 B_2 W_2 = 12를 사용합니다. 따라서 총 생산량은 U_1 + W_1 = 3 단위의 나무 및 U_2 + W_2 = 5 단위의 음식이며, 4 + 16 = 20 인간-시간이 필요합니다.

그러나 더 나은 조직이 가능합니다. 아폴랑카는 3 단위의 나무와 0.5 단위의 음식을 생산할 수 있고, 비들스도르프는 나무를 생산하지 않고 4.5 단위의 음식을 생산할 수 있습니다. 각 리소스의 총 생산량은 동일하지만, 3A_1+0.5A_2+0B_1+4.5B_2 = 3 + 1 + 13.5 = 17.5 인간-시간만 필요합니다.

N = 3인 경우 또 다른 예는 A_1 = 1, B_1 = 2, A_2 = 2, B_2 = 1, A_3 = 1, B_3 = 1 및 U_i = W_i = 1입니다. 이 경우 각 마을은 현재 4 인간-시간을 작업하고 있습니다. 그러나 약간의 재조직으로 인해 정확히 같은 총 리소스를 생산하면서 각각 3 인간-시간을 작업할 수 있습니다. 아폴랑카는 리소스 2의 단위를 하나 덜 생산하고 리소스 1의 단위를 하나 더 생산하면 되고, 비들스도르프는 그 반대로 할 수 있습니다.

이러한 모든 값이 주어진 경우, 마을이 정확히 동일한 총 리소스를 생산하기 위해 필요한 최소 총 인간-시간을 계산할 수 있습니까? 리소스 생산에 투입된 인간-시간의 수는 정수일 필요가 없습니다.