Background

LAOI members created a CSP-J mock contest with $10^{100}$ problems.

2025.1.24 The idea of this problem comes from xzCyanBrad.

Problem Description

The contest uses the ICPC rules: first sort by the number of solved problems in non-increasing order, then sort by the total penalty time in non-decreasing order.

There are $n$ top players coming to speedrun this contest, and the contest lasts $m$ minutes in total.

At the beginning of minute $i$ ($0 \le i \le m-1$), player $s_i$ first submits $t_i$ WA submissions (each adds $x$ minutes of penalty), and then solves one problem. So their solved count increases by $1$, and their total penalty time increases by $x \times t_i + i$ minutes.

Player $i$ has a total of $k_i$ WA submissions and solves $a_i$ problems (it is guaranteed that $\sum_{i=1}^n a_i = m$). Why did they not finish all problems? Because they thought the problems were too easy and not interesting, so they left.

If player $i$ finds that they are in first place on the leaderboard (no ties allowed) after finishing all of their submissions, then we say they "speedrun the contest."

Construct sequences $\{s_m\}$ and $\{t_m\}$ such that player $i$ has exactly $k_i$ WAs and solves exactly $a_i$ problems, and the number of players who "speedrun the contest" is as large as possible.

Input Format

There are three lines in total.

The first line contains three integers $n,m,x$.

The second line contains $n$ integers, representing $\{a_n\}$.

The third line contains $n$ integers, representing $\{k_n\}$.

Output Format

Output the maximum number of players who "speedrun the contest" on the first line.

On the second and third lines, output one optimal construction:

The second line contains $m$ integers, representing $\{s_m\}$.

The third line contains $m$ integers, representing $\{t_m\}$.

3 9 20
3 3 3
0 1 2

3
3 3 3 2 2 2 1 1 1
1 0 1 0 1 0 0 0 0

3 16 3
5 5 6
2 0 8

3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 3
0 0 1 0 0 1 1 0 2 1 0 2 0 0 1 1

Hint

Sample 1 Explanation

At minute $2$, player $3$ finishes submitting, solves $3$ problems, and has penalty time $20 \times 2 + 0 + 1 + 2 = 43$ minutes.

At minute $5$, player $2$ finishes submitting, solves $3$ problems, and has penalty time $20 \times 1 + 3 + 4 + 5 = 32$ minutes.

At minute $8$, player $1$ finishes submitting, solves $3$ problems, and has penalty time $20 \times 0 + 6 + 7 + 8 = 21$ minutes.

Constraints

The testdata is not guaranteed to be random.

This problem uses bundled tests.

For $100\%$ of the testdata, it is guaranteed that:

• $m\ge 3n$；
• $3 \le n\le10^5$；
• $9\le m\le 3\times10^5$；
• $0\le x\le 5\times10^4$；
• $0\le k_i \le 4\times10^4$；
• $3\le\color{black} a_i \le 3\times10^5$；
• $\sum ^{n}_{i=1} a_i = m$。

Translated by ChatGPT 5