What does it mean to have an average rating of at least \(3\) stars? Let’s formulate this condition.
Assume there are originally \(q\) reviews with a total of \(p\) stars.
Furthermore, let’s say we add \(B_i\) reviews with \(i\) stars.
Then, having an average rating of at least \(3\) stars can be formulated as follows:
\(\displaystyle \frac{p+B_1+2B_2+3B_3+4B_4+5B_5}{q+B_1+B_2+B_3+B_4+B_5} \ge 3\)
From here, transforming the formula gives:
\(p+B_1+2B_2+3B_3+4B_4+5B_5 \ge 3 \times (q+B_1+B_2+B_3+B_4+B_5)\)
\(p-3q-2B_1-B_2+B_4+2B_5 \ge 0\)
This equation shows that adding reviews with \(3\) stars or less is pointless or harmful.
By setting \(B_1=B_2=B_3=0\) and further transforming, we get \(B_4+2B_5 \ge 3q-p\).
Now, let’s consider satisfying this equation with the minimum amount of bribery.

Regarding the above equation, “adding \(2\) reviews with \(4\) stars” has the same effect as “adding \(1\) review with \(5\) stars.”
In other words, these two operations can be exchanged for each other.

From here, we can see that the optimal case will be one of the following three:

• Do not add any \(4\)-star reviews. Only add \(5\)-star reviews to raise the average to at least \(3\) stars.
• Add just one \(4\)-star review and some \(5\)-star reviews to raise the average to at least \(3\) stars.
• Only add \(4\)-star reviews to raise the average to at least \(3\) stars.

By trying all the above three cases and printing the minimum amount of bribery, the problem can be solved in a time complexity of \(O(1)\) per test case.

Sample Implementation (C++):

#include<bits/stdc++.h>

using namespace std;

long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while(t>0){
    t--;

    vector<long long> a(8),p(8);
    for(long long i=1;i<=5;i++){cin >> a[i];}
    for(long long i=1;i<=5;i++){cin >> p[i];}

    long long star=0,rev=0;
    for(long long i=1;i<=5;i++){
      star+=a[i]*i;
      rev+=a[i];
    }

    long long res=8e18;
    long long gain=3*rev-star;
    if(gain<=0){res=0;}
    else{
      // all 4*
      res=min(res,gain*p[4]);

      // one 4* + many 5*
      res=min(res,p[4]+llceil(gain-1,2)*p[5]);

      // all 5*
      res=min(res,llceil(gain,2)*p[5]);
    }
    cout << res << "\n";
  }
  return 0;
}