問題一覧 > 通常問題

No.3764 Graduation Live

レベル : / AI推定難易度 : 3050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 3
作問者 : ei1333333 / テスター : kyoprouno ei13333333
お気に入りにしたユーザー ProblemId : 14014 / 自分の提出
問題文最終更新日: 2026-10-09 00:26:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 517 (順位表) の他の問題:

Problem Statement

A group of $3$ people, Yachiyo, Kaguya, and Iroha, will perform a live concert.

For each of the $N$ candidate songs for the concert, "which unit sings it" is specified in advance.

The $i (1 \leq i \leq N)$-th song is one of the following $6$ types.

  • $t_i = 1$: Solo song (Yachiyo). Consumes $1$ of Yachiyo's stamina.
  • $t_i = 2$: Solo song (Kaguya). Consumes $1$ of Kaguya's stamina.
  • $t_i = 3$: Solo song (Iroha). Consumes $1$ of Iroha's stamina.
  • $t_i = 4$: Duet song (Yachiyo & Kaguya). Consumes $1$ of stamina from each of Yachiyo and Kaguya.
  • $t_i = 5$: Duet song (Yachiyo & Iroha). Consumes $1$ of stamina from each of Yachiyo and Iroha.
  • $t_i = 6$: Duet song (Kaguya & Iroha). Consumes $1$ of stamina from each of Kaguya and Iroha.

Also, if the $i$-th song is selected, the audience gains satisfaction $v_i$.

The stamina of Yachiyo, Kaguya, and Iroha is $Y, K, I$, respectively.

You cannot select the same song $2$ or more times, and you cannot make a selection in which the total stamina consumed by any person exceeds $Y, K, I$, respectively.

Let $C$ be the maximum number of songs that can be selected while satisfying these conditions.

For each integer $c\ (1 \leq c \leq C)$, find the maximum total audience satisfaction $X_c$ when selecting a total of $c$ songs.

You are given $T$ test cases; solve each of them.

Constraints

  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 3 \times 10^5$
  • $0 \leq Y, K, I \leq N$
  • $1 \leq t_i \leq 6$
  • $|v_i| \leq 10^9$
  • The sum of $N$ over all test cases is at most $3 \times 10^5$
  • All input values are integers

Input

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$:$
$\mathrm{case}_T$

Here, $\mathrm{case}_i$ is the $i$-th test case, given in the following format.

$N$ $Y$ $K$ $I$
$t_1$ $v_1$
$t_2$ $v_2$
$:$
$t_N$ $v_N$

Output

Print $T$ lines. On the $i$-th line, print the answer to $\mathrm{case}_i$ in the following format.

$C$ $X_1$ $X_2$ $\cdots$ $X_C$

If $C=0$, print only $0$.

Sample

Sample 1
Input
1
6 1 1 1
1 5
2 4
3 3
4 10
5 9
6 8
Output
3 10 13 12

At most $C = 3$ songs can be selected.

When selecting $1$ song, selecting song $4$ gives a total satisfaction of $10$, which is the maximum.

When selecting $2$ songs, selecting songs $3, 4$ gives a total satisfaction of $3+10=13$, which is the maximum.

When selecting $3$ songs, selecting songs $1, 2, 3$ gives a total satisfaction of $5+4+3=12$, which is the maximum.

Sample 2
Input
2
5 2 1 1
1 8
1 8
4 10
5 10
6 9
6 0 2 2
1 100
2 -2
2 -3
3 -4
3 -5
5 -1
Output
3 10 20 25
4 -2 -5 -9 -14

The total satisfaction may be negative.

Sample 3
Input
2
3 3 3 0
3 1
5 2
6 3
3 1 1 1
4 0
5 0
6 0
Output
0
1 0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。