Ben found an old game box in his grandfather's basement and is looking forward to having $$$AGM$$$ (A Great Moment) playing it. In the box he found a game table with $$$12$$$ rows ($$$9-12$$$ are extra) and $$$6$$$ columns, $$$7$$$ types of pieces (which we will further call I, O, L, J, T, S, Z), and a description of the game:
- At he beginning of the game some cells become unavailable.
- In one move, Ben can ROTATE the current piece ONE step clockwise or counterclockwise or he can also MOVE the piece ONE column to the left, ONE column the the right or ONE row down.
- A move is considered VALID if, after performing the move, ALL elements of the piece are ON the table and NONE of the elements of the piece are placed on an unavailable spot.
- Ben can SET a piece ONLY if moving the piece down is not possible, all elements of the piece are on the table and NOT on the extra rows. After a piece is SET, all the spots corresponding to its elements become unavailable.
- As a result of setting a piece, some rows may have been filled with unavailable cells. We call this $$$AGM$$$ (A Great Moment). After an $$$AGM$$$, each of the filled rows on the table (regardless of the moment they were filled) is cleared and all the rows above it are shifted down 1 position. Let $$$R$$$ be the number of cleared rows after an $$$AGM$$$. Then, $$$\frac{R \times (R + 1) \times 100}{2}$$$ points will be added to Ben's score.
- At the very beginning, or when a piece is set, Ben takes the next piece and places it on the table with its origin on the $$$1$$$st column of the $$$12$$$th row. Note that Ben will always use the game pieces in the order that they are given to him by the All Mighty.
- After all the pieces are used, or the current piece cannot be set, the game ends.
Find below a description of each game piece. Notice how each of them fits into a $$$4 \times 4$$$ square matrix. Each black square represents an element of the piece. We'll consider the origin of each piece, the top left corner of this matrix. A rotation of ONE step corresponds to a transition between adjacent states of the same piece.
Ben wonders what is the maximum possible score that can be achieved by correctly using a given set of pieces. Can you help Ben out?
The first line of the input contains the number of game pieces $$$N$$$ ($$$1 \leq N \leq 5$$$).
The second line contains a string of length $$$N$$$ containing the game pieces.
The following $$$8$$$ lines, each contain a string length $$$6$$$. The character '.' signifies an open position on the game table, while the character '#' signifies an unavailable position on the game table. No other characters are used.
The output file should contain one integer representing the maximum possible score which can be obtained through strategic and well planned $$$AGM$$$s (A Great Moments).
4 ZLTI ###..# ###..# ###..# ###..# ###..# ...... ...... #....#
1100
There is a party in town and you would like to attend it. The party theme is bitwise operations! You just knocked on the door and the bodyguard with a big xor-like hat on his head asks you a question in order to let you in. You just heard your favourite song "Se misca pe bit" playing inside, so you need to solve the problem as quick as possible.
You are given a sequence of $$$1 \leq N \leq 10^6$$$ pairwise distinct non-negative integers $$$a_1, a_2, ..., a_N$$$. The value of a subsequence $$$a_i, a_{i+1}, ..., a_j$$$ with $$$i \leq j$$$ is:
where OR is the bitwise OR operator.
You need to calculate the bitwise XOR sum of the values of all subsequences.
The first line of the input will contain the number $$$N$$$ ($$$1 \leq N \leq 10^6$$$), representing the size of the given sequence $$$a$$$. The following line will contain $$$N$$$ pairwise distinct non-negative integers (the array $$$a$$$), where $$$0 \leq a_i \leq 10^{18}$$$ for $$$1 \leq i \leq N$$$.
You should output one line containing one non-negative integer: the bitwise XOR sum of the values of all subsequences.
4 2 1 5 7
5
The value of subsequence:
$$$[2]$$$ is $$$2 \ \textrm{OR} \ 2 = 2$$$
$$$[2, 1]$$$ is $$$2 \ \textrm{OR} \ 1 = 3$$$
$$$[2, 1, 5]$$$ is $$$5 \ \textrm{OR} \ 1 = 5$$$
$$$[2, 1, 5, 7]$$$ is $$$7 \ \textrm{OR} \ 1 = 7$$$
$$$[1]$$$ is $$$1 \ \textrm{OR} \ 1 = 1$$$
$$$[1, 5]$$$ is $$$5 \ \textrm{OR} \ 1 = 5$$$
$$$[1, 5, 7]$$$ is $$$7 \ \textrm{OR} \ 1 = 7$$$
$$$[5]$$$ is $$$5 \ \textrm{OR} \ 5 = 5$$$
$$$[5, 7]$$$ is $$$7 \ \textrm{OR} \ 5 = 7$$$
$$$[7]$$$ is $$$7 \ \textrm{OR} \ 7 = 7$$$
And the XOR sum of these values is $$$5$$$.
The chicken population at a local farm has spiralled out of control, and you are in charge of taking care of it. You may produce one type of food that is characterised by the number of proteins, vitamins and sugars.
For each of the $$$1 \leq N \leq 10^5$$$ chicken, you know one relation for each of the components of the food such that the chicken survives. For each one of the $$$3$$$, you receive an information of type $$$[a, b]$$$ ($$$2 \leq a \leq b \leq 10^4$$$) which means the chicken will survive if the food provided has a value $$$k$$$ of the said component, with $$$a \leq k \leq b$$$.
Besides this, the owner of the farm also gives you $$$1 \leq K \leq 10^5$$$ constraints. These can be of $$$4$$$ types:
- $$$1$$$ $$$a$$$ $$$ b$$$ means at least one of the chickens $$$a$$$ and $$$b$$$ should survive.
- $$$2$$$ $$$a$$$ $$$b$$$ means at least one of the chickens $$$a$$$ and $$$b$$$ should not survive.
- $$$3$$$ $$$a$$$ $$$b$$$ means chicken $$$a$$$ and $$$b$$$ are entangled, so they should both either survive or not.
- $$$4$$$ $$$a$$$ $$$b$$$ means chicken $$$a$$$ and $$$b$$$ are opposite, meaning one should survive and one shouldn't.
After feeding them the food, you may also pick some chicken to eat for dinner if they survived.
You should find a type of food and a configuration for the dinner that satisfy all of the constraints, or tell that it is impossible to do so.
The first line contains then number $$$N$$$ of chicken. The following $$$3*N$$$ lines contain the description of the chicken.
For each chicken, the $$$3$$$ lines will contain two integers which correspond to the relation of that chicken to proteins, vitamins and sugars respectively.
The next line will contain the number $$$K$$$ of constraints. Each of the next $$$K$$$ lines will contain 3 integers, describing one of constraints.
In case there is no solution, you should output one line containing the integer $$$-1$$$.
Otherwise, the first line of the output file should contain $$$3$$$ integers $$$1 \leq P \leq 10^9$$$, $$$1 \leq V \leq 10^9$$$ and $$$1 \leq S \leq 10^9$$$, the characteristics of the food.
The second line should contain the integer $$$D$$$. Following that there should be a line with $$$D$$$ integers, the chicken you will use for dinner.
In case there are multiple correct solutions, you may output any of them.
4 2 5 2 5 2 5 5 10 5 10 5 10 5 5 5 5 5 5 5 5 5 5 5 5 4 2 1 2 4 1 2 1 3 4 3 3 4
5 5 5 1 2
2 2 2 2 2 2 2 3 3 3 3 3 3 2 1 1 2 3 1 2
-1
In 2020, due to $$$issues$$$ worldwide, $$$Cupidonus$$$ moved his tutoring program online. For a small reasonable amount (4000 - 5000 Euros) he can teach you the ways of the $$$cupid$$$, so you will be able to become a $$$Cupidon$$$. Of course inferior to $$$Cupidonus$$$.
As a result $$$N$$$ smarties registered for his program. Since $$$Cupidonus$$$ is really busy, he decided to organize a test in order to select the right candidate in one go. As a result, he aligned all the smarties on the $$$OY$$$ axis and asked each of them to shoot an arrow in the semiplane with $$$x \gt 0$$$. $$$Cupidonus$$$ will select the maximum number of smarties such that any two trajectories of their arrows do $$$NOT$$$ intersect.
$$$Cupidonus$$$ asked you to supervise the test and tell him how many candidates will be selected.
The first line of the input will contain the number of test cases $$$T$$$ ($$$1 \leq T \leq 100000$$$).
The first line of each test case will be the number $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the number of smarties who registered to become a $$$Cupidon$$$.
The following $$$N$$$ lines of each test case will each contain $$$3$$$ integers $$$a_i$$$, $$$x_i$$$, $$$y_i$$$ ($$$-2^{52} \leq a_i, y_i \leq 2^{52}$$$, $$$1 \leq x_i \leq 2^{52}$$$, $$$1 \leq i \leq N$$$), the position of the $$$i$$$th smartie on the $$$OY$$$ axis and the coordinates where his arrow landed. All $$$a_i$$$ are pairwise distinct.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$500000$$$.
The output should contain $$$T$$$ lines, each containing the answer to the corresponding test case.
2 5 6 8 3 -7 8 1 -10 10 -10 0 7 7 -2 2 8 5 2 6 -4 6 1 6 -6 6 -9 -5 7 1 4 4 -3
3 2
For the first example we can choose the smarties with indexes: 2, 3, 5. See image below.
John has to stay indoors for a whole month. He is overwhelmed with boredom and decides to purchase a pocket computer. After evaluating several offers, he chooses a Chinese one, as it is the cheapest. A few days later, the computer arrives and John is thrilled to discover that the device has an interesting gaming function.
The game consists of the computer randomly choosing a positive number $$$ \leq 10^9 $$$. The player has to guess the number only by asking the computer several comparisons with a different number specified by the player which will be answered by the computer with $$$True$$$ or $$$False$$$. After a while, John suspects that there must be some contradictions in the computer's answers, realising that some of the answers are wrong. John wants to know which is the smallest possible number of wrong answers given by the computer without knowing the initial number chosen by the computer.
The first line of the input will contain the number $$$T$$$, representing the number of test cases.
The first line of each test will contain one positive number $$$N$$$, the number of questions asked.
The next N lines will contain one character $$$C$$$, one integer $$$X$$$, $$$|X| \leq 10^9$$$, and one string $$$S$$$. The character $$$C$$$ can be either $$$ \lt $$$, $$$ \gt $$$ or $$$=$$$ and $$$S$$$ is either $$$True$$$ or $$$False$$$.
It is guaranteed that the sum of all questions is smaller than 10^6.
The output file should consist of $$$T$$$ lines, each line containing one integer, the minimum possible number of wrong answers.
Due to the large amount of data in the output, it is recommended to use stream desynchronization, if you are going to write using standard streams in C++.
2 3 = 5 True > 3 True = 1 False 2 > 4 True = 4 True
0 1
In the first test case, if the number the computer chose is 5, then all the questions are answered correctly, so the answer is 0 wrong answers.
In the second test case, both questions cannot be true at the same time, so then the minimum number of wrong answers is 1.
Ghita and Lica decided to play $$$T$$$ friendly games. Since he is competitive, your task is to help Ghita win every single one of them.
In this game, you are given a matrix of $$$N$$$ rows and $$$M$$$ columns. You earn a point by placing a marble in any cell of said matrix. However, there is a rule that Lica has imposed on Ghita and which you must follow - on each row and column, you are only allowed to place a certain amount of marbles at most.
In order for Ghita to win, you must place the marbles in such a way that all the requirements are fulfilled while maximising the total number of points.
The first line has an integer T ($$$1\leq T \leq 10^5$$$) - the number of games.
On the first line of a test's input, there are two integers, namely: $$$N$$$, the number of rows and $$$M$$$, the number of columns.
The second line of input contains N values $$$a_i$$$ ($$$1 \leq i \leq N$$$, $$$0 \leq a_i \leq M)$$$ - the maximum number of marbles that can be placed on row $$$i$$$.
The third line of input contains M positive integers $$$b_j$$$ ($$$1 \leq j \leq M$$$, $$$0 \leq b_j \leq N$$$) - the maximum number of marbles that can be placed on column $$$j$$$.
Please note that the sum of $$$N$$$, respectively the sum of $$$M$$$ will not exceed $$$10^6$$$ over all test cases.
For each test, you ought to print, on a line, a value $$$x$$$ which represents the maximum number of points that can be obtained while satisfying Lica's conditions.
1 4 4 1 1 3 4 2 2 2 4
9
Mickey is a very cheeky boy who recently found two interesting items. The first item is a special type of glue - called SuperGlue and the other one is a very rare rooted tree. The tree itself is binary, which means that all of its nodes are leafs or either having two sons, where a leaf is a node without any sons. Moreover, the tree is that interesting such that it is fully balanced. A tree is fully balanced when:
where $$$l_i$$$ and $$$l_j$$$ are any two leafs in the tree. By $$$dist(i, j)$$$ we mean the distance from node $$$i$$$ to node $$$j$$$.
Mickey was wondering a lot how to combine those two items, and in the end, he decided to take a subtree from the tree (which was not the tree itself) and to glue this one to a leaf which is not part of it. Time flew and Mickey forgot what he has done but now he wants to revert the tree to its original state!
The first line of the input will contain the number of nodes $$$N \leq 15*10^5$$$ of the resulting tree.
The following $$$N-1$$$ lines will each contain an edge between two nodes of the resulting tree.
You should output three numbers on the same line:
- the node representing the root of the original tree.
- the node representing the root of the subtree that was glued; this subtree is defined based on the original root found in the above bullet.
- the node to which the subtree has to be glued to retrieve the original tree.
3 1 2 1 3
2 3 2
The tree from the input is: 
The original tree is as follows: 
Peter is captive in W's maze which can be represented as a tridimensional matrix with lengths $$$N$$$, $$$M$$$ and $$$K$$$. Initially, Peter is in cell (1,1,1) and he needs to get to cell ($$$N$$$,$$$M$$$,$$$K$$$) to escape. From a cell, he can move to any other cell that has a wall in common with your cell (maximum $$$6$$$ other cells). Now, everyone expects Peter to escape in the minimum number of steps, but he can do better than that. He thinks of getting out with the maximum number of steps, such that he doesn't visit a cell more than once in his path. Help Peter find the length of this path!
The first line of the input contains a number $$$1 \leq T \leq 200.000$$$, the number of tests. The next $$$T$$$ lines each contain the description of a test, 3 positive integers $$$1 \leq N, M, K \leq 10^6$$$.
The output should contain $$$T$$$ lines, each containing an answer to a test.
3 1 2 2 10 10 10 190700 80700 150700
3 1000 2319196143000000
Peter the gangster is the new mob boss in the city and wants to grow his affairs as fast as possible. The best way to do that is by collection some pizzo (protection taxes) from influential people that are already protected by other mob bosses. Peter can establish friendship relations with any mob for some amount of money. One person may have multiple mobsters protecting him. To be able to get money from a person, Peter needs first to be friend with the mobsters protecting him.
Given for each person the amount of money he is able to pay and for each mobster the amount of money requested for his friendship, find the maximum amount of money Peter can collect.
The first line of the input contains 2 numbers, $$$1 \leq N \leq 100$$$ (the number of mob bosses) and $$$1 \leq M \leq 100$$$ (the number of influential people).
The next line contains $$$N$$$ numbers representing the amount of money each mob requests for his friendship.
The next line contains $$$M$$$ numbers representing the amount of money each person is able to pay.
The next $$$M$$$ lines will contain, for each person $$$i$$$, the number $$$k_i$$$, the number of mobsters protecting person $$$i$$$, followed by $$$k_i$$$ numbers representing the mobsters protecting person $$$i$$$.
Any amount of money in the input is a positive integer $$$\leq 5000$$$.
The output should contain a number containing the maximum amount of money Peter can collect.
5 5 7 10 3 1 6 5 2 3 9 7 1 3 1 4 1 2 3 1 2 3 1 4
10
5 8 19 15 18 7 8 13 9 8 5 8 5 10 5 1 5 3 1 2 3 2 1 3 1 4 2 1 5 2 1 5 4 1 2 3 5 1 1
5
Dorian found an old mouse laying around the house and is now playing around with it. Dorian's mousepad can be modeled as a matrix with $$$N$$$ rows and $$$M$$$ columns such that $$$N * M \leq 10^5$$$. Each cell of the mousepad is either clean which is represented by a $$$0$$$, or dirty which is represented by a $$$1$$$.
He quickly realised $$$2$$$ things: the mouse can only be moved horizontally and vertically and it only registers a movement if it realised between $$$2$$$ adjacent cells that are both clean!
Now Dorian thought of an interesting game: starting from the top left of the matrix, without lifting his mouse from the mousepad and without going outside the bounds, can he trick the mouse into thinking it was moved to some other arbitrary coordinates $$$-10^5 \leq X \leq 10^5$$$ and $$$-10^5 \leq Y \leq 10^5$$$?
You should output a sequence of instruction composed of characters $$$L(eft)$$$, $$$R(ight)$$$, $$$U(p)$$$, $$$D(own)$$$ if it is possible to reach the said coordinates, or $$$-1$$$ otherwise.
Keep in mind the $$$Y$$$ coordinate increases as you go up in the matrix, and the $$$X$$$ coordinate increases as you go right. The mouse initially thinks it is at coordinates $$$(0, 0)$$$ and you start from the top left corner of the matrix.
There is also something strange about Dorian's mousepad, because its extremities are made of a special material, they never get dirty. That is, first and last rows and columns will always be clean.
The first line will contain two integers $$$N$$$ and $$$M$$$: the dimensions of the mousepad.
The following $$$N$$$ lines will each contain a string of $$$M$$$ characters, the description of the mousepad.
The last line will contain two integers $$$X$$$ and $$$Y$$$, the coordinates Dorian wants to reach.
For each testcase, you should output one line either a $$$-1$$$ if there is no solution, or a string of no more than $$$10^6$$$ characters: the instructions for Dorian.
5 5 00000 01000 01000 01000 00000 2 3
DRDDLDRUDRULDRULDRULUURULDRULD
These are the coordinates registered by the mouse after each move:
(1,0), (1,0), (1,0), (1,0), (1,0), (1,1), (1,2), (1,3), (2,3)
In a long forgotten realm, there are $$$1 \leq N \leq 2 \times 10^5$$$ houses positioned in a 2D plane. House number $$$i$$$ has coordinates $$$(x_i, y_i)$$$, where $$$0 \leq x_i \leq 2 \times 10^9$$$ and $$$0 \leq y_i \leq 2 \times 10^9$$$. In this kingdom, houses are generally not too close to each other. We know that for every house, there exist at most $$$T \leq 20$$$ houses within distance $$$R \leq 2 \times 10^9$$$ from it, where the distance function is the squared Euclidean distance. Formally, the squared Euclidean distance is defined as $$$dist((x_i, y_i), (x_j, y_j)) = (x_i - x_j)^2 + (y_i - y_j)^2$$$. Below, it is understood that a neighbour of a house is another house within squared Euclidean distance R from it.
Since being around neighbours is important for safety purposes, we call a house "safe" if it has at least $$$K \leq 10$$$ neighbours. Travelling from a safe house to another neighbouring safe house is safe and encounters a danger level of 0. Besides travelling between reachable safe houses, there also exist $$$1 \leq M \leq 5 \times 10^5$$$ forest roads, each joining a pair of houses $$$(i, j)$$$ with a total danger corresponding to the squared Euclidean distance between houses $$$i$$$ and $$$j$$$. It is guaranteed that getting between any pair of houses is possible. Note that it is only possible to travel between neighbouring safe houses or using the forest road system.
The king of this magical kingdom occasionally reviews the danger of traveling throughout his empire. The danger of a path between houses $$$i$$$ and $$$j$$$ is defined as the maximum danger encountered on any given road part of this path. The king has just asked his advisors to figure out for $$$1 \leq Q \leq 2 \times 10^5$$$ pairs of cities what is the minimum danger a citizen will encounter, should they choose an optimal path.
Knowing they will not be able to tackle such a phenomenal task, the king's advisors enlist your help!
The first line of the input will contain $$$6$$$ numbers: $$$N$$$, $$$R$$$, $$$K$$$, $$$T$$$, $$$M$$$, $$$Q$$$ as defined above.
The following $$$N$$$ line will contain $$$2$$$ numbers each: $$$x_i$$$ and $$$y_i$$$, the coordinates of house $$$i$$$.
The next $$$M$$$ lines each contain $$$2$$$ numbers $$$i$$$, $$$j$$$ meaning there is a 2 way forest road edge between $$$i$$$ and $$$j$$$.
The following $$$Q$$$ lines each contain a pair of numbers $$$i$$$ and $$$j$$$ meaning that you are asked to compute the minimal danger of getting from house $$$i$$$ to house $$$j$$$.
For each testcase, you should output one line containing one integer: the minimum danger for the corresponding query. The answer is guaranteed to fit in a 64 bits number.
8 25 2 20 2 3 10 10 8 7 9 11 13 8 12 10 20 10 22 11 19 9 1 6 1 8 3 4 2 7 3 8
0 82 82
Note that houses 1 - 5 are all "safe" houses since each house has at least 2 neighbours within distance 25. In fact, it is possible to get from every house to every other house with 0 danger. Similarly, houses 6 - 8 are also safe houses and mutually reachable.
The cost of getting from house $$$2$$$ to house $$$4$$$ is 0 since it is possible to get from house $$$2$$$ to its safe neighbour house $$$1$$$ and then from house $$$1$$$ to its neighbour house $$$4$$$.
Getting from house $$$2$$$ to house $$$7$$$ optimally can be done by going from house $$$2$$$ to house $$$1$$$ with a cost 0, then going from house $$$1$$$ to house $$$8$$$ with a $$$82$$$ cost using a forest road and then finally going from house $$$8$$$ to its safe neighbour house $$$7$$$. The maximum on this path is $$$82$$$.
Getting from house $$$3$$$ to house $$$8$$$ can be done by going to house $$$1$$$ with cost 0 and from house $$$1$$$ to house $$$8$$$ with cost $$$82$$$.
The AGM realm consists of $$$1 \leq N \leq 10^5$$$ cities, indexed from $$$1$$$ to $$$N$$$. This year there is a special sunrise, so everyone wants to see it. The sunrise can be seen just from the city D. The cities from AGM realm are connected with $$$N$$$ directed roads and each road is of type $$$1$$$ or type $$$2$$$. Each city $$$i$$$ has cars of power $$$1 \leq val_i \leq 2*10^5$$$. Everyone wants to travel from their city to city $$$D$$$ using the cars. If you are using a car with power $$$x$$$, the cost to traverse a road of type $$$1$$$ is $$$x$$$, and the cost to traverse a road of type $$$2$$$ is $$$x^2$$$. If you start your journey from city $$$i$$$, you will start with a car of power $$$val_i$$$. When reaching a city $$$j$$$ on your route you have the opportunity to change your car with one of power $$$val_j$$$ with a cost of $$$-10^{13} \leq tax_j \leq 10^{13}$$$. The journey stops as soon as you reach city $$$D$$$, but you can still change your car in this city. You can't change the car in the city where you start the journey from.
For each city $$$1 \leq i \leq N$$$, you need to compute the minimum cost to reach city $$$D$$$ starting from city $$$i$$$. It is guaranteed that city $$$D$$$ is reachable from all the cities.
The first line of the input will contain the number $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of cities, and the number $$$D$$$ ($$$1 \leq D \leq N$$$), representing the city where the sunrise can be seen.
The following $$$N$$$ lines will contain two numbers $$$x_i$$$ ($$$1 \leq x_i \leq N$$$, $$$x_i \neq i$$$) and $$$t_i$$$ ($$$1 \leq t_i \leq 2$$$) each, representing that there exists a directed road from city $$$i$$$ to city $$$x_i$$$ of type $$$t_i$$$.
The line $$$N + 1$$$ will contain $$$N$$$ numbers, the array $$$val$$$ ($$$1 \leq val_i \leq 2*10^5$$$). Where $$$val_i$$$ represents the power of the cars from city $$$i$$$.
The line $$$N + 2$$$ will contain $$$N$$$ numbers, the array $$$tax$$$ ($$$-10^{13} \leq tax_i \leq 10^{13}$$$). Where $$$tax_i$$$ represents the cost to change the car in city $$$i$$$.
You should output one line consisting of $$$N$$$ numbers, representing the minimum cost to reach city D starting from city $$$i$$$, for each $$$1 \leq i \leq N$$$ (Note that this cost can be negative too).
5 3 2 1 3 2 1 2 1 2 2 1 5 2 6 3 1 -10 4 -4 -1 3
9 0 0 8 -2
The journey with minimum cost from city 4:
You start with a car with power 3 and travel to city 1 with this power, it will cost you $$$3^2 = 9$$$.
In city 1 you change the car with one with power 5 and it will cost you -10.
Then you travel to city 2 with this power, it will cost you 5.
In city 2 you change the car with one with power 2 and it will cost you 4.
Then you travel to city 3 with this power, it will cost you $$$2^2 = 4$$$.
And in city 3 you change the car and it will cost you -4.
The total cost of the journey is 8.