### PROBLEM LINK:

**Author:** Kaushik Iska

**Tester:** Anton Lunyov

**Editorialist:** Anton Lunyov

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

None

### PROBLEM:

It is the best described in the problem statement.

### QUICK EXPLANATION:

For each level **L** let’s calculate the total power of Soints of this level and the same for Sofloats. Let it be **SointsPower[L]** and **SofloatsPower[L]** respectively. Then if **SointsPower[L]** strictly less than **SointsPower[L]** we add the difference **SofloatsPower[L] − SointsPower[L]** to the answer. Doing this for all **L** we get the final answer.

### EXPLANATION:

Though the previous explanation seems to be obvious it still requires some justification. **If you understand it clearly you can skip this paragraph.** Let’s consider the difference **SofloatsPower[L] − SointsPower[L]** introduced above. Clearly, it remains the same after each fight at this level. Also it is clear that if both numbers **SofloatsPower[L]** and **SointsPower[L]** are positive then the fight at the level **L** is possible and these two numbers decreases after the fight. So the battle ends once for each level one of these numbers equal to zero, while other will be equal to the absolute difference of the initial values of these two numbers. Clearly if **SofloatsPower[L] > SointsPower[L]** then in the end there will be no Soints of level **L** but at least one Sofloat of level **L** will remain. On the other hand, if **SofloatsPower[L] ≤ SointsPower[L]** then there will be no Sofloats of level **L** in the end of the battle. Hence SoChef should give at least **SofloatsPower[L] − SointsPower[L]** additional chakra to Soints of level **L** if this difference is positive and it also will be sufficient. Hence the answer coincides with that described above.

Now let’s discuss an implementation of this solution. Since levels are positive integers up to 100 we can create an arrays **SointsPower[]** and **SofloatsPower[]** with meaning described above initially filled by zeros:

for L from 1 to 100 SointsPower[L] = 0 SofloatsPower[L] = 0

We can fill them just during the reading the information about warriors. That is, if numbers **C** and **L** was read for the current Soint we should simply increase **SointsPower[L]** by **C**:

read C, L SointsPower[L] = SointsPower[L] + C

The same should be made for Sofloats. After that in one loop over all possible levels we calculate the answer:

ans = 0 for L from 1 to 100 dif = SofloatsPower[L] − SointsPower[L] if dif > 0 then ans = ans + dif print ans

So we get the solution with time complexity **O(N + M + L)** and memory **O(L)**. You can see an implementation of this approach in author’s solution.

### ALTERNATIVE SOLUTION:

Let’s save all information about warriors in, say, 4 arrays of numbers. Then iterate over all levels from 1 to 100 and for each level **L** create a variable **dif** initially set to 0 and iterate over all Soints and over all Sofloats. If Soint of level **L** is met decrease **dif** by power of this Soint. If Sofloat of level **L** is met increase **dif** by power of this Sofloat. If in the end **dif > 0** then increase answer by **dif**. Clearly in this way we find the answer. This solution has time complexity **O(L * (N + M))** and requires **O(N + M)** memory. So it is slower then the previous one but easily passes the time limit.

We can improve this solution. For this let’s sort all warriors by level and then iterate over all warriors by groups of the same level and do the same as above with **dif**. In this way we get a solution with complexity **O((N + M) * log (N + M))** and the same memory if we use some fast sorting algorithm like Quicksort or Merge sort. You can see an implementation of this approach in tester’s solution.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.