The problem statement is the title of the problem.

Re-read the original announcement blog.

If you carefully read the announcement blog, you will notice that I especially thanked BucketPotato for testing. Just print "BucketPotato".

print("bucketpotato")

Did you notice the peculiar constraints on the variable $$$r$$$?

"Mike" is of course MikeMirzayanov. "Mike's sequence" has to do with Codeforces ratings.

3000 is the cutoff for the highest rating: Legendary Grandmaster.

Mike's sequence are the Codeforces rating thresholds: [1200,1400,1600,1900,2100,2300,2400,2600,3000]. Your task is simply to print the threshold immediately above the provided rating $$$r$$$.

R = int(input())
ratings = [1200,1400,1600,1900,2100,2300,2400,2600,3000]
higher = [r for r in ratings if r > R]
print(higher[0])

Aenar Targaryen was a dragonlord of Old Valyria.

The main clue is the title: "Pōja Verdon".

Aenar Targaryen was a dragonlord of Valyria (an empire from a A Song of Ice and Fire) who moved his family to Westeros right before Valyria was destroyed.

pōja means their and verdon means sum (or amount based on context) in High Valyrian (you can easily translate this on Duolingo).

In a nutshell: Print the sum of the array.

n = int(input())
nums = list(map(int,input().strip().split()))
print(sum(nums))

Did you notice that the problem had a special "constraints" section? That's highly unusual for a Codeforces problem.

The length of S is 3. Are there any famous three letter programming contests?

The capital variable letters and the "constraints" section are designed to mimic how atcoder.jp formats their problem statements.

The problem is asking whether the Atcoder contest (ABC,ARC,AGC) is rated for a rating $$$X$$$. (Note that the judge ignores Atcoder heuristic contests for simplicity).

• ABC's are rated for $$$[0,1999]$$$
• ARC's are rated for $$$[0,2799]$$$
• AGC's are rated for $$$[1200,\infty]$$$

s = input().strip()
x = int(input().strip())
if (s=="ABC" and x<2000) or (s=="ARC" and x<2800) or (s=="AGC" and x>=1200):
    print('yes')
else:
    print('no')

Do you recognize the story of the Minotaur?

The problem is a word search, but not for the word "minotaur".

Perhaps you recognize the story of the minotaur? Less known is the hero who saved the kids from the minotaur: his name was Theseus [thee-see-us].

The problem is just a word search (horizontal, vertical, diagonal) for theseus. You should only go in the forward direction when you search for a word.

The grid contains other clues embedded in it. Perhaps you can find esoteric, java, and script (hints for problem G). You might be able to find atcoder (hint for problem D). Also hero (hinting at Theseus for this problem).

There are also some red herring words out there.

#include <bits/stdc++.h>
using namespace std;

void good() {
    cout << "YES";
    exit(0);
}

int main() {
    int N; cin >> N;
    char grid[N][N];
    for (int i = 0; i < N; i++) {
        string row; cin >> row;
        for (int j = 0; j < N; j++) grid[i][j] = row[j];
    }

    string word = "theseus";
    for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i < N-7) {
				string w = "";
				for (int k = 0; k < 7; k++) w += grid[i+k][j];
				if (w == word) good();
			}
			if (j < N-7) {
				string w = "";
				for (int k = 0; k < 7; k++) w += grid[i][j+k];
				if (w == word) good();
			}
			if (i < N-7 && j < N-7) {
				string w = "";
				for (int k = 0; k < 7; k++) w += grid[i+k][j+k];
				if (w == word) good();
			}
		}
    }
    cout << "NO";
}

Where is the quote from?

"buffy", "the", "vampire", "slayer"

"buffy" (length 5), "the" (length 3), "vampire" (length 7), "slayer" (length 6). Remember how $$$3 \le |s| \le 7$$$? Now go back to the sample and see what you can do.

The quote is from the well known TV series Buffy the Vampire Slayer.

Perhaps you notice the lengths of the words buffy, the, vampire, slayer are unique integers in the set {3,5,6,7}.

Given the string $$$s$$$, simply "add" that string with the target word of the same length.

Here's how adding two letters work:

1. Convert both letters to numbers in $$$[0,25]$$$.
2. Add the two numbers up modulo 26.
3. Convert the number back into a letter.

You can verify your addition algorithm is correct by checking whether "tourist" + "vampire" = "ooggqjx" (as provided in the sample).

Finally, if the length of $$$s$$$ is $$$4$$$, the answer is "none", because there is no word of length 4 in Buffy the Vampire Slayer.

s = input().strip()
words = ["","","","the","","buffy","slayer","vampire"]
if len(s)==4:
    print("none")
else:
    target = words[len(s)]
    ans = ""
    for i in range(len(s)):
        a = ord(s[i])-ord('a')
        b = ord(target[i])-ord('a')
        ans += chr((a+b)%26 + ord('a'))
    print(ans)

Input is a normal string of letters, but output consists of non-letter characters?

Think of an esoteric programming language.

JSF (an esoteric programming language equivalent to Javascript that only uses 6 characters).

The April Fool's Contests love of esoteric programming languages, combined with the reference to "six characters", will eventually lead you to JSFuck.

The six characters is a pun: the input is a string of length 6 like "abcdef", but the output is a string \textit{consisting} of only 6 characters: [ ] ( ) ! +.

Brief research will demonstrate a mapping from each english letter to a JSFuck string. Two letters can be concatenated with "+".Note that the optimal mapping will make your solution file approximately 12KB in size, well within the 64KB requirement of Codeforces.

However, the mapping from each letter to javascript is not unique! However, the legend mentions that Aenar needs to go to the string's "home". JSFuck's home website is here, which is where the jury's mapping is created from.

Alternatively, instead of hardcoding the generated strings, you can simply use the encoding algorithm provided in the Github.

Hard-coding strings: 152393980

Algorithmically generating strings (in Javascript): 152398972 (credit to BigDelta)

Google research into how Pascal and C++ work will eventually lead you to a solution like this. Many people used the fact that \ can be used to continue single line comments to the next line in C++ but not in Pascal.

// \
begin end.
int main() {}

Fix $$$a$$$ into a convenient constant.

Since $$$P \ge 5$$$ and is also a prime number, we know that $$$P-1$$$ is an even composite number. A even composite number is guaranteed to have at least 2 unique divisors greater than 1. Let two of these divisors be $$$a$$$ and $$$b$$$. It is guaranteed that $$$P\mod{a} = P\mod{b} = 1$$$, and thus this selection is valid.

For example, we can simply pick $$$a=2$$$ and $$$b=P-1$$$, and we will get a correct solution.

The time complexity is $$$\mathcal{O}(Q)$$$.

There a very limited number of squares where each of Gregor's pawns could end up.

Identify a greedy strategy to maximize the answer.

The key insight is that due to the fact that there is only one row of enemy pawns, and those pawns never move, there are only $$$3$$$ possible columns where one of Gregor's pawns can end up in.

We can solve this problem greedily, going from column $$$1$$$ to column $$$N$$$. At the current column $$$j$$$, if Gregor has a pawn in this column, then we greedily consider 3 cases.

• If there is an uncaptured enemy pawn in column $$$j-1$$$, mark that pawn as captured and increment the answer. Column $$$j-1$$$ will never be looked at again, so this decision is optimal.
• If there is no pawn in column $$$j$$$, just move Gregor's pawn forward, and increment the answer.
• If there is an uncaptured enemy pawn in column $$$j+1$$$, mark that pawn as captured and increment the answer.
• Otherwise, this pawn will not reach the first row.

This greedy solution is guaranteed to produce the maximum possible answer.

The time complexity is $$$\mathcal{O}(N)$$$.

Write the problem as a graph problem.

Valid captures or valid forward moves represent edges in the graph.

We have two sets: Gregor's pawns, and destination squares. We also have some edges between these two sets.

Maximum Matching.

Each of Gregor's pawns can end up in one of 3 possible squares. If Gregor has a pawn in column $$$i$$$, it can end up in column $$$i-1$$$ or $$$i+1$$$ if there is an enemy pawn in those columns. Furthermore, it can remain in column $$$i$$$ if there is no enemy pawn in that column.

Let's build a graph $$$G$$$, where each edge connects one of Gregor's pawns to a valid destination cell. Since every edge goes from a cell in the bottom row to a cell in the top row, $$$G$$$ is clearly bipartite. It's now clear that moving as many pawns to the end is equivalent to finding a maximum matching in $$$G$$$.

The time complexity is $$$\mathcal{O}(N\sqrt{N})$$$ using the HKK algorithm for maximum matching. ($$$G$$$ has at most $$$2N$$$ vertices, and $$$6N$$$ edges)

For various graphs, try and simulate the process. Determine a rule to figure out whether a noble survives or not.

When you add or remove a single edge, how much can the answer change by? Try and recalculate the answer in $$$\mathcal{O}(1)$$$.

Due to the queries, actually simulating the process each time will be too expensive.

Proof that the Process will End: Assume after round $$$x$$$, $$$x_i$$$ nobles are killed. If $$$x_i=0$$$, then the state of the graph doesn't change, so the process will have ended. If $$$x_i > 0$$$, then the number of nobles decreases. Thus, the maximum number of rounds the process can last is $$$N$$$, so it must end.

$$$\textbf{Lemma 1:}$$$ At the end of the process, no two nobles will still be friends.

Proof by Contradiction: Assume that nobles $$$u$$$ and $$$v$$$ (assume WLOG that $$$u < v$$$) are still friends and the process is over. In order for $$$u$$$ to avoid being killed, there must be a noble $$$w$$$ weaker than $$$u$$$ that is also a friend of $$$u$$$. The same logic then applies to $$$w$$$, and we have an infinite descent argument. There are only a finite number of nobles weaker than $$$u$$$, so there will be a contradiction.

$$$\textbf{Lemma 2:}$$$ If all of a noble's friends are weaker than it, that noble cannot be killed.

Direct Proof: Since none of the noble's friends are stronger than it, it is impossible for $$$\textit{all}$$$ of them to be stronger at any point in the process.

$$$\textbf{Final Idea:}$$$ By combining Lemmas 1 and 2, we can prove that if ALL of a noble's friends are weaker than it, that noble survives, otherwise it will die. This leads to the solution.

Maintain in an array the number of nobles weaker than noble $$$i$$$. Since the updates guarantee that the edge being removed/added does/doesn't exist respectively, we only need to keep track of the number of edges of each noble. Essentially, a noble survives if and only if weaker[i]==edges[i]. After linear precomputation, updates and queries take constant time.

The time complexity is $$$\mathcal{O}(N+M+Q)$$$.

Let's say the subarray $$$A_i \dots A_j$$$ is all congruent to $$$n\mod{m}$$$. What does that imply about the subarray?

What does the previous hint imply about the difference array generated by $$$D[i]=A[i+1]-A[i]$$$?

GCD

The key observation is to construct the difference array $$$D$$$ of size $$$N-1$$$, where $$$D[i]=abs(A[i+1]-A[i])$$$. If a given subarray is a friend group, then every difference is a multiple of some $$$m$$$. Since every element of $$$A$$$ is distinct, the case when $$$D[i]=0$$$ can be ignored.

We can now convert this into a GCD (greatest common divisor) problem. It follows that $$$A[i\dots j]$$$ is a friend group if and only if $$$\gcd{(D[i\dots j-1])} > 1$$$. Indeed, the value $$$m$$$ that we want is equal to this GCD.

To solve the problem, we can use a sparse table or a segment tree to find the largest possible subarray beginning at $$$i$$$, and then max over all subarray answers to get the final answer.

The time complexity is $$$\mathcal{O}(N\log{N}\log{10^{18}})$$$. The first log is for the sparse table, the second is for computing GCDs.

Note that the de facto time complexity may be closer to $$$\mathcal{O}(N\log{N}+N\log{10^{18}})$$$, due to the insights from this blog post.

Convert the word problem into a combinatorics equation.

Write the equation for some $$$x$$$. Write the equation for $$$x+1$$$. How can we easily transition from the first to the second equation?

For a given $$$x$$$, we want to calculate every third term in the sequence $$$\binom{i}{x}$$$ for $$$i \in [1,3N]$$$. Think about how computing the entire summation $$$\sum_{i=1}^{3N}{\binom{i}{x}}$$$ will help.

For a given $$$x$$$, we want to compute $$$\sum_{i=1}^{N}{\binom{3i}{x}}$$$, which can be solved with a combinatorial dynamic programming.

Define the array dp[x][m] (dimensions: $$$N+1\times 3$$$), which computes the sum $$$\sum_{i=0}^{N-1}{\binom{3i+m}{x}}$$$. Under this definition, $$$ans[x]=dp[x][0]+\binom{3N}{x}$$$, where ans is what we want to find.

Under the definition of the dp, we can make the following mathematical observations.

$$$dp[x][0]+dp[x][1]+dp[x][2]=\sum_{i=0}^{3N-1}{\binom{i}{x}}$$$, since term $$$i$$$ belongs to the array with $$$m=i\mod{3}$$$. This summation can be condensed with the Hockey Stick Identity into $$$\binom{3N}{x+1}$$$.

By repeated uses of Pascal's Identity, we get equations (2) and (3), giving us a system of 3 equations with 3 new unknowns, which can easily be solved.

1. $$$\sum_{m=0}^{2}{dp[x][m]}=\binom{3N}{x+1}$$$.
2. $$$dp[x][1] = dp[x][0]+dp[x-1][0]$$$
3. $$$dp[x][2] = dp[x][1]+dp[x-1][1]$$$

The base case is that $$$dp[0][0]=dp[0][1]=dp[0][2]=N$$$. Each query can now be answered trivially.

The time complexity is $$$\mathcal{O}(N+Q)$$$ with combinatorial precomputation.

Convert the word problem into a combinatorics equation.

How will the Binomial Theorem be helpful?

Try and construct a polynomial $$$P(k)$$$ such as the coefficient $$$k^x$$$ in that polynomial represents the number of attack plans if the wolf wants to eat $$$x$$$ pigs.

Notice that $$$P(k)$$$ is a geometric series, so FFT is unnecessary.

Define the polynomial $$$P(k)=(1+k)^3+(1+k)^6+\cdot + (1+k)^{3N}$$$.

The coefficient of $$$k^x$$$ in $$$P(k)$$$ is, by the Binomial theorem on each term of the polynomial, equal to $$$\binom{3}{x}+\binom{6}{x}+\dots + \binom{3N}{x}$$$. This is equal to ans[x] from the previous solution.

The only thing left to do is quickly calculate $$$P(k)$$$. Due to the tight time limit, calculating the polynomial using FFT in $$$\mathcal{O}{(N\log{N})}$$$ is probably too slow.

Instead, we notice that $$$P(k)$$$ is a geometric series. Using the geometric series formula, we get that $$$P(k)=\frac{(1+k)^{3N+3}-(1+k)^3}{(1+k)^3-1}$$$.

The numerator and denominator of this fraction can be expanded in linear time. Then all we have to do is a polynomial long division. Once we have $$$P(k)$$$, we can answer all the queries trivially.

The time complexity is $$$\mathcal{O}(N)$$$ with combinatorial precomputation.

"Enclosed cows" are just interior points. It's clear that Pick's Theorem will be useful.

Manipulate Pick's Theorem into a modular equation.

The number of boundary points between $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\gcd{(x_1-x_2,y_1-y_2)}$$$.

Working with relevant formulas, find a simple condition between two points, such that they can be treated as equivalent.

Every set of 3 fenceposts forms a lattice triangle We want to find the number of such lattice triangles that have an odd number of interior points. Since all the coordinates are even, the area is automatically even as well. By Pick's Theorem, $$$area=I+\frac{B}{2}-1$$$, so $$$2\cdot area=2I+B-2$$$. $$$I$$$ is the number of interior points, and $$$B$$$ is the number of boundary points, for an arbitrary triangle formed by 3 fenceposts.

Let $$$A=2\cdot area$$$, so $$$A=2I+B-2$$$. Since $$$I$$$ is odd, taking both sides modulo 4 we get that $$$A \equiv B\mod{4}$$$. Since the area is an even integer, $$$A$$$ is a multiple of 4, so we get that $$$A\equiv B\equiv 0\mod{4}$$$.

Let's define the $$$\textbf{boundary count}$$$ of a segment to be the number of lattice points on it, minus 1. It can be proven that the boundary count of the segment connecting $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\gcd{(|x_2-x_1|,|y_2-y_1|)}$$$.

In this problem, we only care about what the boundary count is modulo 4. Since all the coordinates are even, the GCD is guaranteed to be even, so the boundary count is either 0 or 2 mod 4. For the segment connecting $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ call its boundary count $$$b$$$.

• $$$b\equiv 0\mod{4}$$$ IFF $$$x_1\equiv x_2 \mod{4}$$$ AND $$$y_1\equiv y_2 \mod{4}$$$.
• $$$b\equiv 2\mod{4}$$$ in all other situations.

$$$\textbf{Key Idea:}$$$ Turn fence post $$$(x,y)$$$ into $$$(x\mod{4},y\mod{4})$$$.

Writing the area of a triangle via the shoelace formula, it becomes obvious that the area mod 4 won't change when the coordinates are modded by 4. Additionally, by our work above, $$$B$$$ (the sum of the boundary counts for the 3 sides of the triangle) is entirely dependent on the coordinates mod 4.

Let cnt[x][y] be an array counting the number of points that fall into each category based on the key idea above. Since all coordinates are even, only 4 elements in the $$$cnt$$$ array will be nonzero. We can fix each point of the triangle into one of the categories, quickly calculuate $$$A$$$ and $$$B$$$, and solve the problem. Be careful not to overcount triangles.

The time complexity is $$$\mathcal{O}(N)$$$, with a small constant for the counting.

Solve the easy version of the problem.

Taking each coordinate modulo 4 no longer works. This is because if $$$\Delta{x}$$$ or $$$\Delta{y}$$$ are odd, there's no way to predict whether the boundary count (see editorial of the easy version) is 1 or 3 mod 4.

By playing with Pick's Theorem, you should find that $$$B$$$ (the total number of boundary points) has to be even. Let $$$b_1$$$, $$$b_2$$$, and $$$b_3$$$ be the boundary count of the three sides of a lattice triangle.

Lets count the answer. Fix a point. Fix the boundary count mod 4 of the two sides adjacent to that point. Fix more things.

In Hint 4, we fixed a point. It's critical that you fix the boundary count of the side opposite that point to be even.

First read (and understand!) the editorial for the easy version of the problem.

• Definition: The $$$\textbf{modularity}$$$ of a point (x,y) is (x%4,y%4).
• Definition: The $$$\textbf{boundary count}$$$ of a segment is the number of lattice points on that segment, minus 1.

Lets precompute the array cnt[i][x][y][b] (dimensions $$$N\times 4\times 4\times 4$$$), which equals the number of other points respective to points[i] with modularity $$$(x,y)$$$ and with a boundary count mod 4 equal to $$$b$$$. This precomputation can be done in $$$\mathcal{O}(N^2 \log{10^7})$$$ time, by iterating over every pair of points. The boundary count of the segment $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ is $$$\gcd{(|x_2-x_1|,|y_2-y_1|)}$$$.

Consider the number of boundary points on the three sides of a triangle, and call them $$$b_1,b_2,b_3$$$. Clearly, $$$B=b_1+b_2+b_3$$$. The key idea is that since $$$B$$$ is even, wlog we can assume that $$$b_3$$$ is even, and that $$$b_1 \equiv b_2 \mod{2}$$$. The other key idea is that it is easy to figure out if the boundary count is congruent to 0 or 2 mod 4 based on the modularities of the coordinates alone, but it's impossible if the boundary count is odd.

Let's fix a point, and count the number of triangles that involve this point. Let's also iterate over all the relevant modularities of the other two points in the triangle, which range from $$$(0,0)$$$ up to $$$(3,3)$$$. Let's also make sure that there are an even number of boundary points on the side opposite the fixed point, which we know almost nothing about. It can be shown that $$$b_3 \equiv 0\mod{4}$$$ IFF $$$(x_1,y_1)=(x_2,y_2)$$$, and that $$$b_3 \equiv 2\mod{4}$$$ IFF $$$x_1,x_2$$$ have the same parity, and $$$y_1,y_2$$$ have the same parity, and the previous case doesn't apply. Finally, make sure that the parity of the boundary count of the two sides next to the fixed point are the same.

Using the precomputed array $$$cnt$$$ and the formula for $$$b_3$$$, we can quickly find $$$B$$$ in this case. Using the Shoelace Formula, we can quickly find what $$$A$$$ is modulo 4. If $$$A$$$ is even and equal to $$$B$$$, then we know that $$$I$$$ must be odd (in the easy version of the problem, we found that $$$A \equiv B \mod{4}$$$ IFF $$$I$$$ is odd), so all triangles in this class are interesting. Thus, we add to the answer a number roughly equal to $$$cnt[i][x_1][y_1][b_1]\cdot cnt[i][x_2][y_2][b_2]$$$ (it could be lower due to the potential overcount, if two points fall into the same bucket of the array).

Lastly, be sure not to overcount triangles! In my code, I count each of the EEE triangles ($$$b_1,b_2,b_3$$$ all even) 3 times, and the OOE triangles once.

The time complexity is $$$\mathcal{O}(N^2 \log{10^7})$$$ (the main part of the solution is approximately $$$\mathcal{O}(512N)$$$).

Implementation Note: The bottleneck of the algorithm is computing the GCDs. The simplest optimization that is sufficient for AC is to only calculate $$$\frac{N^2}{2}$$$ GCDs instead of all $$$N^2$$$ (since the GCD is commutative). Java requires additional optimizations, such as precomputing small GCDs.

Let's give each component a "representative" cell. Then our task is now to count the number of representatives.

Let the cell with the smallest amount of paint in a component be the representative. How can we find if a given cell $$$(i,j)$$$ is a representative or not?

This editorial was written by Benq, and inspired by 1392I - Кевин и сетка.

For simplicity let's assume that all $$$a_i$$$ are distinct (and similarly, all $$$b_j$$$). If this is not the case, we may break ties arbitrarily.

Say that two badly painted cells are directly reachable from each other if they are in the same row or column and all cells in between them are also badly painted. Also, define the value of the cell at $$$(i,j)$$$ to be $$$a_i+b_j$$$. Call a badly painted cell a $$$\textbf{representative}$$$ if no cell directly reachable from it has a smaller value than it.

$$$\textbf{Claim:}$$$ Every connected component of badly painted cells contains exactly one representative.

$$$\textbf{Proof:}$$$ Clearly every connected component contains at least one representative; consider the cell(s) with the minimum value contained within it. To show that every connected component contains \textit{exactly} one representative, suppose that we are given a representative $$$(i,j)$$$ that is directly reachable from $$$(i',j)$$$ for all $$$i_l\le i'\le i_r$$$ and $$$(i,j')$$$ for all $$$j_l\le j'\le j_r$$$, where $$$a_i=\min_{i_l\le i'\le i_r}(a_{i'})$$$ and $$$b_j=\min_{j_l\le j'\le j_r}(b_{j'})$$$. Then the connected component containing $$$(i,j)$$$ is completely contained within the rectangle $$$[i_l,i_r]\times [j_l,j_r]$$$, and $$$(i,j)$$$ is the unique cell with the minimum value within that rectangle. This implies that a representative is always the unique cell with the minimum value within its connected component.

It remains to count the number of representatives. For each $$$i$$$, let $$$lo_i$$$ be the maximum index less than $$$hi_i$$$ such that $$$a_{lo_i}<a_i$$$ and $$$hi_i$$$ be the minimum index greater than $$$i$$$ such that $$$a_{hi_i}<a_i$$$. Then define $$$na_i$$$ to be $$$\min(\max_{i'\in [lo_i,i]}a_{i'},\max_{i'\in [i,hi_i]}a_{i'})$$$. Any path from a cell in row $$$i$$$ to a cell in the same column with lower value must pass through a row with value at least $$$na_i$$$. Define $$$nb_j$$$ for each $$$j$$$ similarly. It can be shown that $$$(i,j)$$$ is a representative if and only if the following conditions hold:

• $$$a_i+b_j\le X$$$
• $$$na_i+b_j>X$$$
• $$$a_i+nb_j>X$$$

Computing $$$na$$$ and $$$nb$$$ can be done in $$$\mathcal{O}(N\log N+M\log M)$$$ with any data structure supporting range min/max queries (e.g. sparse tables), or in $$$O(N+M)$$$ with a stack.

It remains to count the number of pairs $$$(i,j)$$$ that satisfy these conditions given $$$a$$$, $$$na$$$, $$$b$$$, and $$$nb$$$. First initialize two binary indexed trees $$$T_a$$$ and $$$T_b$$$. Then sort the pairs $$$(na_i-a_i,a_i),(nb_j-b_j,b_j)$$$ in decreasing order. Now for every pair in the order, if it is of the form $$$(na_i-a_i,a_i)$$$, then add to the answer the number of elements of $$$T_b$$$ that are in the range $$$(X-na_i,X-a_i]$$$, and add $$$a_i$$$ to $$$T_a$$$. The reasoning for the case $$$(nb_j-b_j,b_j)$$$ is similar (query $$$T_a$$$, update $$$T_b$$$).

The time complexity is $$$\mathcal{O}(N\log{N}+M\log{M})$$$ for sorting the pairs and working with the two BITs.