Chef's friend Alex runs a movie theatre. Due to the increasing number of platforms for watching movies online, his business is not running well. As a friend, Alex asked Chef to help him maximise his profits. Since Chef is a busy person, he needs your help to support his friend Alex.

Alex's theatre has four *showtimes*: 12 PM, 3 PM, 6 PM and 9 PM. He has four movies which he would like to play ― let's call them A, B, C and D. Each of these movies must be played exactly once and all four must be played at different showtimes. For each showtime, the price of a ticket must be one of the following: Rs 25, Rs 50, Rs 75 or Rs 100. The prices of tickets for different showtimes must also be different.

Through his app, Alex receives various requests from his customers. Each request has the form "I want to watch this movie at this showtime". Let's assume that the number of people who come to watch a movie at a given showtime is the same as the number of requests for that movie at that showtime.

It is not necessary to accommodate everyone's requests ― Alex just wants to earn the maximum amount of money. There is no restriction on the capacity of the theatre. However, for each movie that is not watched by anyone, Alex would suffer a loss of Rs 100 (deducted from the profit).

You are given $\ufffd$ requests Alex received during one day. Find the maximum amount of money he can earn on that day by choosing when to play which movies and with which prices.

### Input

- The first line of the input contains a single integer $\ufffd$ denoting the number of test cases. The description of $\ufffd$ test cases follows.
- The first line of each test case contains a single integer $\ufffd$.
- $\ufffd$ lines follow. Each of these lines contains a character $\ufffd$, followed by a space and an integer $\ufffd$, describing a request to see the movie $\ufffd$ at the showtime $\ufffd$.

### Output

For each test case, print a single line containing one integer ― the maximum profit Alex can earn (possibly negative).

Finally, print a line containing one integer ― the total profit over all test cases, i.e. over $\ufffd$ days.

### Constraints

- $1\le \ufffd\le 150$
- $0\le \ufffd\le 100$
- $\ufffd$ is 'A', 'B', 'C' or 'D'
- $\ufffd$ is $12$, $3$, $6$ or $9$

### Subtasks

Subtask #1 (30 points): it is possible to fulfill all requests

Subtask #2 (70 points): original constraints

### Sample 1:

5 12 A 3 B 12 C 6 A 9 B 12 C 12 D 3 B 9 D 3 B 12 B 9 C 6 7 A 9 A 9 B 6 C 3 D 12 A 9 B 6 2 A 9 B 6 1 D 12 0

575 525 -25 -200 -400 475

### Explanation:

Example case 1: The following table shows the number of people that want to watch the movies at the given showtimes:

12 | 3 | 6 | 9 | |
---|---|---|---|---|

The maximum number of requests was sent for movie B at 12 PM. Therefore, we play this movie at this time and the tickets cost Rs 100. Next, we play movie D at 3 PM with ticket price Rs 75 and movie C at 6 PM with ticket price Rs 50. Finally, we have a slot for 9 PM and the only movie we can play at that time now is movie A, with ticket price Rs 25. The total profit is $3\cdot 100+2\cdot 75+2\cdot 50+1\cdot 25=300+150+100+25=575$. Since each movie was watched by at least one person, there is no additional loss.

Example case 2: Just like above, we show the requests in a table:

12 | 3 | 6 | 9 | |
---|---|---|---|---|

The optimal solution is to play movie A at 9 PM, movie B at 6 PM, movie C at 3 PM and movie D at 12 PM, with decreasing ticket prices in this order. The profit is $3\cdot 100+2\cdot 75+1\cdot 50+1\cdot 25=300+150+50+25=525$.

Example case 3: Again, we show the requests in a table:

12 | 3 | 6 | 9 | |
---|---|---|---|---|

The optimal solution is to play movie A at 9 PM with ticket price Rs 100, movie B at 6 PM with ticket price Rs 75 and the remaining two movies in any order at 12 PM and 3 PM ? either way, there will be nobody watching them. We earn $1\cdot 100+1\cdot 75=175$, but we have to deduct Rs 200, so the resulting profit is $175-200=-25$.

Example case 4: The optimal solution is to play movie D at 12 PM; the other three movies go unattended. We have to deduct Rs 300, so the profit is $1\cdot 100-300=-200$.

Example case 5: Since there are no requests for any movie at any time, all movies go unattended and Alex just suffers a loss of Rs 400.

The total profit for all 5 days is $575+525-25-200-400=475$.

Code(C++):-

__Code(JAVA):-import java.util.*;import java.lang.*;import java.io.*;__

/* Name of the class has to be "Main" only if the class is public. */class Codechef{ static ArrayList<String> list; static void allComb(String s, String r){ if(s.length()==0){ list.add(r); return; } for(int i=0;i<s.length();i++){ allComb(s.substring(0,i)+s.substring(i+1,s.length()),r+s.charAt(i)); } } public static void main (String[] args) throws java.lang.Exception { // your code goes here BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); list = new ArrayList<>(); int t = Integer.parseInt(br.readLine()); ArrayList<Integer> res = new ArrayList<>(); allComb("ABCD",""); for(int q=0;q<t;q++){ int n = Integer.parseInt(br.readLine().trim()); int[][] a = new int[4][4]; if(n==0){ res.add(-400); System.out.println(-400); } else { for(int i=0;i<n;i++){ String[] s=br.readLine().split(" "); char ch=s[0].charAt(0); int m=Integer.parseInt(s[1]); if(m==12){ a[ch-'A'][0]++; } else if(m==3){ a[ch-'A'][1]++; } else if(m==6){ a[ch-'A'][2]++; } else{ a[ch-'A'][3]++; } } int max=Integer.MIN_VALUE; for(int i=0;i<24;i++){ String curr=list.get(i); int sum=0; int pro=100; List<Integer> temp=new ArrayList<>(); for(int j=0;j<4;j++){ temp.add(a[curr.charAt(j)-'A'][j]); } Collections.sort(temp,Collections.reverseOrder()); for(int j=0;j<4;j++){ if(temp.get(j)==0){ sum+=-100; } else{ sum+=temp.get(j)*pro; pro-=25; } } max=Math.max(max,sum); } res.add(max); System.out.println(max); } } int profit=0; for(int i=0;i<t;i++){ profit+=res.get(i); } System.out.println(profit); }}

__Code(JAVA):-import java.util.*;import java.lang.*;import java.io.*;__

/* Name of the class has to be "Main" only if the class is public. */class Codechef{ static ArrayList<String> list; static void allComb(String s, String r){ if(s.length()==0){ list.add(r); return; } for(int i=0;i<s.length();i++){ allComb(s.substring(0,i)+s.substring(i+1,s.length()),r+s.charAt(i)); } } public static void main (String[] args) throws java.lang.Exception { // your code goes here BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); list = new ArrayList<>(); int t = Integer.parseInt(br.readLine()); ArrayList<Integer> res = new ArrayList<>(); allComb("ABCD",""); for(int q=0;q<t;q++){ int n = Integer.parseInt(br.readLine().trim()); int[][] a = new int[4][4]; if(n==0){ res.add(-400); System.out.println(-400); } else { for(int i=0;i<n;i++){ String[] s=br.readLine().split(" "); char ch=s[0].charAt(0); int m=Integer.parseInt(s[1]); if(m==12){ a[ch-'A'][0]++; } else if(m==3){ a[ch-'A'][1]++; } else if(m==6){ a[ch-'A'][2]++; } else{ a[ch-'A'][3]++; } } int max=Integer.MIN_VALUE; for(int i=0;i<24;i++){ String curr=list.get(i); int sum=0; int pro=100; List<Integer> temp=new ArrayList<>(); for(int j=0;j<4;j++){ temp.add(a[curr.charAt(j)-'A'][j]); } Collections.sort(temp,Collections.reverseOrder()); for(int j=0;j<4;j++){ if(temp.get(j)==0){ sum+=-100; } else{ sum+=temp.get(j)*pro; pro-=25; } } max=Math.max(max,sum); } res.add(max); System.out.println(max); } } int profit=0; for(int i=0;i<t;i++){ profit+=res.get(i); } System.out.println(profit); }}

__Recommended Post ____:-__

__Recommended Post__

__:-__

__HCL Coding Questions:-__

__Capgemini Coding Questions:-__

__iMocha coding Questions:-__

__Tech Mahindra coding questions:-__

__Unthinkable Solutions coding questions:-__- Swap the adjacent characters of the string
- Double the vowel characters in the string
- Character with their frequency
- Program to find the closest value

__Must check this:-__

__Companies interview:-__- Swap adjacent characters
- Double the vowel characters
- Check valid parenthesis
- Print the characters with their frequencies
- Find closest value
- Word Count
- Program of CaesarCipher
- Program to find the perfect city
- Annual Day | Tech Mahindra coding question
- Find the number of pairs in the array whose sum is equal to a given target.

__Full C course:- __

__Key points:-__

- How to set limit in the floating value in python
- What is boolean data type
- How to print any character without using format specifier
- How to check that given number is power of 2 or not
- How to fix limit in double and floating numbers after dot (.) in c++
- How to print a double or floating point number in scientific notation and fixed notation
- How to take input a string in c
- How to reduce the execution time of program in c++.

__Cracking the coding interview:-__

__Array and string:-__

__Tree and graph:-__

__Hackerearth Problems:-__

- Very Cool numbers | Hacker earth solution
- Vowel Recognition | Hackerearth practice problem solution
- Birthday party | Hacker earth solution
- Most frequent | hacker earth problem solution
- program to find symetric difference of two sets
- cost of balloons | Hacker earth problem solution
- Chacha o chacha | hacker earth problem solution
- jadu and dna | hacker earth solution
- Bricks game | hacker earth problem
- Anti-Palindrome strings | hacker earth solution
- connected components in the graph | hacker earth data structure
- odd one out || hacker earth problem solution
- Minimum addition | Hackerearth Practice problem
- The magical mountain | Hackerearth Practice problem
- The first overtake | Hackerearth Practice problem

__Hackerrank Problems:-__- Playing With Characters | Hackerrank practice problem solution
- Sum and Difference of Two Numbers | hackerrank practice problem solution
- Functions in C | hackerrank practice problem solution
- Pointers in C | hackerrank practice problem solution
- Conditional Statements in C | Hackerrank practice problem solution
- For Loop in C | hackerrank practice problem solution
- Sum of Digits of a Five Digit Number | hackerrank practice problem solution
- 1D Arrays in C | hackerrank practice problem solution
- Array Reversal | hackerrank practice problem solution
- Printing Tokens | hackerrank practice problem solution
- Digit Frequency | hackerrank practice problem solution
- Calculate the Nth term | hackerrank practice problem solution

__Data structure:-__

- Program to find cycle in the graph
- Implementation of singly link list
- Implementation of queue by using link list
- Algorithm of quick sort
- stack by using link list
- program to find preorder post order and inorder of the binary search tree
- Minimum weight of spanning tree
- Preorder, inorder and post order traversal of the tree

__ MCQs:-__