Submission #20,873

20873

2026-01-10 18:01:42

python3

Accepted 80/80

414ms

18256 KiB


n, m = map(int, input().split())
megbizasok = n * [(0, 0)]
dolgozott = n * [False]
for i in range(m):
    nap, penz = map(int, input().split())
    if penz > megbizasok[nap - 1][0]:
        megbizasok[nap - 1] = (penz, i + 1)

dp = n * [0]
dp[0] = megbizasok[0][0]
for i in range(1, n):
    if i == 1:
        if dp[0] >= megbizasok[1][0]:
            dp[1] = dp[0]
        else:
            dp[1] = megbizasok[1][0]
    else:
        if dp[i - 1] >= dp[i - 2] + megbizasok[i][0]:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 2] + megbizasok[i][0]

j = n - 1
while j >= 0:
    if j == 0:
        if dp[0] > 0:
            dolgozott[0] = True
        break
    elif j == 1:
        if dp[1] == megbizasok[1][0] and megbizasok[1][0] > 0:
            dolgozott[1] = True
        elif dp[1] == dp[0] and dp[0] > 0:
            dolgozott[0] = True
        break
    else:
        if dp[j] == dp[j - 2] + megbizasok[j][0] and dp[j] != dp[j - 1]:
            dolgozott[j] = True
            j -= 2
        else:
            j -= 1

print(dp[-1], dolgozott.count(True))
ids = []
for i in range(n):
    if dolgozott[i]:
        ids.append(megbizasok[i][1])
print(' '.join(map(str, ids)))

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	16ms	3128 KiB
		2	Accepted	234ms	5428 KiB
subtask2	10/10
		3	Accepted	16ms	3124 KiB
		4	Accepted	16ms	3016 KiB
		5	Accepted	16ms	3124 KiB
		6	Accepted	16ms	3124 KiB
		7	Accepted	17ms	3320 KiB
subtask3	10/10
		8	Accepted	16ms	3264 KiB
		9	Accepted	16ms	3124 KiB
		10	Accepted	16ms	3124 KiB
		11	Accepted	16ms	3112 KiB
		12	Accepted	16ms	3208 KiB
subtask4	10/10
		13	Accepted	16ms	3124 KiB
		14	Accepted	16ms	3016 KiB
		15	Accepted	16ms	3124 KiB
		16	Accepted	16ms	3124 KiB
		17	Accepted	17ms	3320 KiB
		18	Accepted	17ms	3120 KiB
		19	Accepted	16ms	3152 KiB
		20	Accepted	17ms	3252 KiB
		21	Accepted	16ms	3028 KiB
		22	Accepted	17ms	3312 KiB
subtask5	10/10
		23	Accepted	16ms	3264 KiB
		24	Accepted	16ms	3124 KiB
		25	Accepted	16ms	3124 KiB
		26	Accepted	16ms	3112 KiB
		27	Accepted	16ms	3208 KiB
		28	Accepted	21ms	3528 KiB
		29	Accepted	21ms	3436 KiB
		30	Accepted	24ms	3308 KiB
		31	Accepted	24ms	3380 KiB
		32	Accepted	26ms	3380 KiB
subtask6	10/10
		33	Accepted	16ms	3124 KiB
		34	Accepted	16ms	3016 KiB
		35	Accepted	16ms	3124 KiB
		36	Accepted	16ms	3124 KiB
		37	Accepted	17ms	3320 KiB
		38	Accepted	16ms	3264 KiB
		39	Accepted	16ms	3124 KiB
		40	Accepted	16ms	3124 KiB
		41	Accepted	16ms	3112 KiB
		42	Accepted	16ms	3208 KiB
		43	Accepted	17ms	3120 KiB
		44	Accepted	16ms	3152 KiB
		45	Accepted	17ms	3252 KiB
		46	Accepted	16ms	3028 KiB
		47	Accepted	17ms	3312 KiB
		48	Accepted	21ms	3528 KiB
		49	Accepted	21ms	3436 KiB
		50	Accepted	24ms	3308 KiB
		51	Accepted	24ms	3380 KiB
		52	Accepted	26ms	3380 KiB
		53	Accepted	27ms	3312 KiB
		54	Accepted	27ms	3380 KiB
		55	Accepted	26ms	3380 KiB
		56	Accepted	27ms	3576 KiB
		57	Accepted	28ms	3576 KiB
subtask7	10/10
		58	Accepted	16ms	3124 KiB
		59	Accepted	16ms	3016 KiB
		60	Accepted	16ms	3124 KiB
		61	Accepted	16ms	3124 KiB
		62	Accepted	17ms	3320 KiB
		63	Accepted	16ms	3264 KiB
		64	Accepted	16ms	3124 KiB
		65	Accepted	16ms	3124 KiB
		66	Accepted	16ms	3112 KiB
		67	Accepted	16ms	3208 KiB
		68	Accepted	17ms	3120 KiB
		69	Accepted	16ms	3152 KiB
		70	Accepted	17ms	3252 KiB
		71	Accepted	16ms	3028 KiB
		72	Accepted	17ms	3312 KiB
		73	Accepted	21ms	3528 KiB
		74	Accepted	21ms	3436 KiB
		75	Accepted	24ms	3308 KiB
		76	Accepted	24ms	3380 KiB
		77	Accepted	26ms	3380 KiB
		78	Accepted	27ms	3312 KiB
		79	Accepted	27ms	3380 KiB
		80	Accepted	26ms	3380 KiB
		81	Accepted	27ms	3576 KiB
		82	Accepted	28ms	3576 KiB
		83	Accepted	195ms	10788 KiB
		84	Accepted	195ms	10800 KiB
		85	Accepted	186ms	10700 KiB
		86	Accepted	192ms	10672 KiB
		87	Accepted	188ms	11060 KiB
subtask8	20/20
		88	Accepted	16ms	3124 KiB
		89	Accepted	16ms	3016 KiB
		90	Accepted	16ms	3124 KiB
		91	Accepted	16ms	3124 KiB
		92	Accepted	17ms	3320 KiB
		93	Accepted	16ms	3264 KiB
		94	Accepted	16ms	3124 KiB
		95	Accepted	16ms	3124 KiB
		96	Accepted	16ms	3112 KiB
		97	Accepted	16ms	3208 KiB
		98	Accepted	17ms	3120 KiB
		99	Accepted	16ms	3152 KiB
		100	Accepted	17ms	3252 KiB
		101	Accepted	16ms	3028 KiB
		102	Accepted	17ms	3312 KiB
		103	Accepted	21ms	3528 KiB
		104	Accepted	21ms	3436 KiB
		105	Accepted	24ms	3308 KiB
		106	Accepted	24ms	3380 KiB
		107	Accepted	26ms	3380 KiB
		108	Accepted	27ms	3312 KiB
		109	Accepted	27ms	3380 KiB
		110	Accepted	26ms	3380 KiB
		111	Accepted	27ms	3576 KiB
		112	Accepted	28ms	3576 KiB
		113	Accepted	195ms	10788 KiB
		114	Accepted	195ms	10800 KiB
		115	Accepted	186ms	10700 KiB
		116	Accepted	192ms	10672 KiB
		117	Accepted	188ms	11060 KiB
		118	Accepted	405ms	18164 KiB
		119	Accepted	414ms	18164 KiB
		120	Accepted	386ms	18244 KiB
		121	Accepted	375ms	18160 KiB
		122	Accepted	407ms	18168 KiB
		123	Accepted	404ms	18028 KiB
		124	Accepted	386ms	18160 KiB
		125	Accepted	368ms	18256 KiB
		126	Accepted	375ms	18168 KiB
		127	Accepted	370ms	18168 KiB