“The early bird gets the first worm, but the wisest bird gets the fastest one.”
Aditya is really fond of playing PUBG. He is constantly finding ways to improve his game so that he can beat his friends Rohan and Raghav. Rohan and Raghav have been playing PUBG since a year. So, both of them know how to win through practice. Aditya, on the other hand is a newbie. But, Aditya is smart. So, he is finding smart ways to win.
The game has started. Aditya has to collect guns from various scattered places.
You are being given the directions to collect the guns. Aditya has limited space in his bag. He has to follow the directions till the end and return back to the beginning to collect the guns. He has to choose the appropriate gun in order to maximise his killing efficiency.
A set of directions consists of several instructions. The first instruction is of the form "Start on XYZ", indicating the street that the route begins on. The next instruction is of the form “Left on abc” indicating the next road after collecting the gun.
Can you help Aditya figure out the best guns he can collect?
The first line of the input consists of a single integer T denoting the number of test cases.
The second line consists of an integer M which denotes the maximum weight of gun he can carry , an integer Z which denotes the total number of roads he has been to and integer N which denotes the total number of guns.
The third line contains N inputs of weights of the gun wt[i] and the fourth line contains corresponding power of those guns p[i].
The following Z lines give instructions showing his route:-
First line consists of the first road. The second line consists of the second road (along with change in direction).
Similar lines follow.
Print Z lines containing his way back to the beginning road with the last traversed road as the first road and vice versa.
And the last line = Sum of the power of guns he can carry in horsepower.
1 <= T <= 10^2
1 <= M <= 10^2
1 <= Z <= 10^3
1 <= N <= 10^4
1 <= wt[i] <= 10^2
1 <= p[i] <= 10^3
1 <= Length[roadname] <= 10^3
50 4 3
10 20 30
60 100 120
Start on xyz
Left on abc
Right on efg
Left on hgf
Start on hgf
Right on efg
Left on abc
Right on xyz
The directions given are to be traced back in the opposite direction and printed.
The maximum weight he can carry is 50. So, the best way possible is to carry the guns with weights 20 and 30. So, total power is 100+120 = 220.