Three problems
Practice
4.4 (7 votes)
Algorithms
Basics of greedy algorithms
Greedy algorithms
Problem
83% Success 1634 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

You are given $$n$$ problems. The problems are of three types, 'Type1', 'Type2', and 'Type3'. There are $$t1$$ 'Type1' problems, $$t2$$ 'Type2' problems, and $$t3$$ 'Type3' problems. You can solve each problem using any of the three methods, 'A', 'B', and 'C'. You can use a particular method only a limited number of times that is, method 'A' for $$a$$ times, method 'B' for $$b$$ times, and method 'C' for $$c$$ times. 

You are given a \(3\times 3\) matrix $$A$$ where $$A[i][j]$$ represents the effort to solve a Type $$i$$ problem using Method $$j$$. You are required to find the minimum effort required to solve all the problems.

Input format

  • The first line contains an integer $$T$$ denoting the number of test cases.
  • The first line of each test case contains an integer $$n$$ denoting the number of problems.
  • The second line of each test case contains three space-separated integers denoting the values of $$t1$$, $$t2$$, and $$t3$$ respectively.
  • The third line of each test case contains three space-separated integers denoting the values of $$a$$, $$b$$, and $$c$$ respectively.
  • Next three lines of each test case contain three space-separated integers of matrix $$A$$.

Output format

For each test case, print the minimum effort required to solve all the problems in a new line.

Constraints

\(1 \le T \le 5\\ 1 \le n \le 1e9\)

\(0 \le t1,\ t2,\ t3 \le 1e9\) (sum of $$t1$$, $$t2$$, and $$t3$$ is equal to $$n$$)

\(0 \le a,\ b,\ c \le 1e9\) (sum of $$a$$, $$b$$, and $$c$$ is equal to $$n$$)

\(1 \le A[i][j] \le 1e9\ (1 \le i,\ j \le 3)\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
78 votes
Tags:
ApprovedEasyGreedy AlgorithmsMathOpen
Points:30
10 votes
Tags:
SortingAlgorithmsBasics of Greedy AlgorithmsGreedy Algorithms
Points:30
57 votes
Tags:
Basic ProgrammingBit ManipulationBit manipulationMathSorting