QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139150#3006. Heaps of Funkaruna#AC ✓64ms231344kbC++171.7kb2023-08-12 18:28:122023-08-12 18:28:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-12 18:28:15]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:231344kb
  • [2023-08-12 18:28:12]
  • 提交

answer

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

typedef long long ll;

const int MAXN = 310;
const int MOD = 1e9 + 7;

ll _pow(ll a, ll x) {
	ll r = 1;
	while (x) {
		if (x & 1) r = r * a % MOD;
		a = a * a % MOD;
		x /= 2;
	}
	return r;
}

int n, a[MAXN], sub[MAXN];
vector<int> b;
vector<int> g[MAXN];

ll inv[MAXN];
ll dp[MAXN][MAXN][MAXN];
ll tmp[MAXN][MAXN];
void dfs(int v) {
	for (int i = 1; i <= a[v]; i++) {
		dp[v][i][1] = (b[i] - b[i - 1]) * _pow(b[a[v]], MOD - 2) % MOD;
	}
	sub[v] = 1;
	for (int x : g[v]) {
		dfs(x);
		for (int s = 0; s <= sub[v]; s++) {
			for (int t = 0; t <= sub[x]; t++) {
				for (int i = 1; i <= a[v]; i++) {
					tmp[i][s + t] = (tmp[i][s + t] + dp[v][i][s] * dp[x][i][t]) % MOD;
				}
			}
		}
		sub[v] += sub[x];
		for (int i = 1; i <= a[v]; i++) {
			for (int j = 0; j <= sub[v]; j++) {
				dp[v][i][j] = tmp[i][j];
				tmp[i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= a[v]; i++) {
		for (int j = 1; j <= sub[v]; j++) {
			dp[v][i][j] = dp[v][i][j] * inv[j] % MOD;
		}
	}
	for (int i = (int)b.size(); i >= 0; i--) {
		dp[v][i][0] = dp[v][i + 1][0];
		for (int j = 1; j <= sub[v]; j++)
			dp[v][i][0] = (dp[v][i][0] + dp[v][i + 1][j]) % MOD;
	}
}
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	for (int i = 1; i < MAXN; i++) 
		inv[i] = _pow(i, MOD - 2);
	cin >> n;
	int r = -1;
	for (int i = 1; i <= n; i++) {
		int x, p; cin >> x >> p;
		if (p == 0)
			r = i;
		else
			g[p].push_back(i);
		a[i] = x;
		b.push_back(x);
	}
	b.push_back(0);
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
	}
	dfs(r);
	cout << dp[r][0][0];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 70448kb

input:

92
28701027 12
925341819 12
2261666 45
669601626 45
101359065 13
539500751 47
731398771 60
7638406 43
537094738 60
32248003 22
149195453 45
745987717 92
70093 92
56067991 76
5621221 47
388528561 85
385998525 12
668685623 45
664589085 92
273920428 35
495594345 60
919398 12
69316963 92
112530446 13
47...

output:

276308373

result:

ok answer is 276308373

Test #2:

score: 0
Accepted
time: 1ms
memory: 40764kb

input:

49
978849904 25
14962340 3
690410213 38
427590 36
2107732 25
495630688 19
862419 37
662343318 6
31779 10
105833 27
235371600 37
190741738 14
663360519 43
760762254 16
237938919 16
73261931 5
821884697 13
640272965 0
450418932 18
776336 9
5640519 45
4319166 43
955422367 42
880885058 28
13991175 29
54...

output:

409304936

result:

ok answer is 409304936

Test #3:

score: 0
Accepted
time: 4ms
memory: 127260kb

input:

169
19 59
562 54
321 114
83 88
162 140
804700 80
11 133
2 35
55 55
1 46
27 43
63 11
2942 115
124 116
45 6
3 160
5 106
622258 78
19 140
3 118
13517 105
35700 18
394 81
43 146
81 129
23 59
1484 30
23 148
644 92
10 135
2 127
54 151
64 64
674 132
10 160
10 95
43324 71
9375 85
2 76
23 88
6 89
3 106
247 1...

output:

294199944

result:

ok answer is 294199944

Test #4:

score: 0
Accepted
time: 28ms
memory: 208116kb

input:

273
4441920 36
730462584 206
414571905 8
358509 121
733386607 260
763671861 100
734487871 227
5519061 113
164565622 244
324955557 43
63209615 97
1220890 173
333825184 209
531319277 193
345347050 54
640358831 59
7740691 251
532124586 146
733909800 213
869407902 258
415248617 42
786775544 60
880789416...

output:

790988061

result:

ok answer is 790988061

Test #5:

score: 0
Accepted
time: 15ms
memory: 216060kb

input:

288
56 268
2 100
5058 162
2 192
7091121 104
9 92
24583 42
65 288
8 57
28153930 80
3 168
210 256
77892 218
1 267
24 272
68 128
49681 71
9281 189
8 185
6 274
1 19
522 92
4 226
40 97
32 235
724 230
3 215
799 39
758 281
1 9
2 184
1 70
505085 65
328664 9
390 268
1 122
89123 112
4 278
10 29
32337 239
28 1...

output:

733701677

result:

ok answer is 733701677

Test #6:

score: 0
Accepted
time: 16ms
memory: 211636kb

input:

284
5 95
5 81
91 190
306 52
943 247
842 207
682 212
5 107
230 45
97 256
2 148
74375 283
9218 213
248 232
975916 142
10 147
9282 150
6 3
600 81
3665 64
63032 103
60 86
290048 104
72 259
99 46
84527 257
677 69
2 21
508 54
9507 99
3 275
23 220
1253 205
711 103
5 150
82 148
9 162
340 144
700 1
65793 105...

output:

781153666

result:

ok answer is 781153666

Test #7:

score: 0
Accepted
time: 3ms
memory: 195800kb

input:

280
23 235
6 139
13 263
7 189
8 120
5 55
8 136
9 12
4 240
84 255
9 195
2 255
82 159
10 255
8 197
6 127
6 245
8 29
5 87
6 82
16 246
8 275
10 77
2 246
2 12
3 197
6 29
50 255
54 255
60 255
8 269
3 12
9 275
59 12
6 29
6 197
401 246
3 255
82 77
8 246
8 275
40 195
4 255
7 255
10 192
4 122
6 255
8 29
10 19...

output:

834244731

result:

ok answer is 834244731

Test #8:

score: 0
Accepted
time: 3ms
memory: 189132kb

input:

254
958 227
9 5
39 29
466 208
371 239
3 113
511 69
6 228
7447 153
216 178
7 69
50 159
5 4
10 244
9 6
48 236
8 58
8 153
46 73
3 234
790 105
1 248
18 183
573 76
4 27
1979 109
394 48
71 51
8386 77
56 110
52 131
9 173
52 154
10 120
9283 0
206 3
6 11
596 72
7 195
83 214
364 190
40364 241
6 86
6 247
1 22
...

output:

190780742

result:

ok answer is 190780742

Test #9:

score: 0
Accepted
time: 12ms
memory: 165244kb

input:

214
584135506 146
4808620 95
211939674 89
373066 123
213650 180
8986 158
3945 115
5685013 168
238530248 24
3457187 51
19672794 96
3431 103
95770226 126
27096357 210
598245 111
94506592 64
630759161 169
59306019 105
7769439 138
258421704 11
4636424 151
42533826 149
3848946 96
4796702 153
8090722 180
...

output:

164167796

result:

ok answer is 164167796

Test #10:

score: 0
Accepted
time: 3ms
memory: 53280kb

input:

67
76196504 54
80391014 37
615505608 40
312401339 3
266807795 40
439948668 54
982472966 54
1920976 15
88245055 37
526090257 54
842957467 54
89569882 54
49752849 40
816472153 40
97007769 54
40234208 40
636326094 47
64785290 54
98448051 54
10675887 22
443479295 22
63932943 54
788463607 54
23806468 54
...

output:

814322641

result:

ok answer is 814322641

Test #11:

score: 0
Accepted
time: 0ms
memory: 92876kb

input:

119
743201368 23
81668356 66
644438847 69
425453633 30
6873300 108
393932908 22
749146122 41
925376911 100
193977775 49
632938984 36
911399140 112
412427109 85
77791324 69
800811311 113
79708730 89
66946569 29
52389600 32
92896460 79
2913930 61
807551468 93
37870741 90
226418 108
309299211 4
6844302...

output:

813293132

result:

ok answer is 813293132

Test #12:

score: 0
Accepted
time: 4ms
memory: 160348kb

input:

215
2 176
5 59
6 38
10 82
5 68
8 169
9 210
4 203
1 193
5 164
3 73
6 175
480 169
4 163
465 23
5 200
6 191
4 142
8 174
66 47
2 154
4 60
9 169
10 181
2 128
4 2
60 196
9 177
4 184
40 6
10 59
8 18
10 164
6 128
3 44
229 137
17 204
97 176
10 178
10 130
15 197
4 35
13 116
6 104
9 145
81 35
2 194
6 3
9 74
70...

output:

679689664

result:

ok answer is 679689664

Test #13:

score: 0
Accepted
time: 1ms
memory: 75040kb

input:

94
16 25
1 77
104 49
6 91
22 28
2 92
9 84
10 41
3 6
6 0
1 34
4 18
2 72
5 89
1 9
6 15
2 66
76 42
9211 28
5 86
2 32
26 30
70 87
5 18
1 37
5 24
73 8
1 15
146 48
98 12
9 32
3 56
4 64
1 7
7 77
4 82
21 46
41 86
46 21
4 63
724 50
1 19
3 33
44 61
4 40
1 29
529 80
7 10
2 8
9 84
2 80
4 61
848 42
1 65
118 31
3...

output:

959062140

result:

ok answer is 959062140

Test #14:

score: 0
Accepted
time: 1ms
memory: 201464kb

input:

266
2 141
2 177
10 27
2 104
25 85
5 183
7 94
8 79
2 63
8 168
2 85
2 27
2 177
95 22
47 27
2 72
5 30
73 79
12 250
2 177
9 203
9 72
57 184
7 123
6 109
8 241
4 207
20 63
4 192
6 79
3 250
4 207
5 207
5 72
10 85
3 27
8 179
3 184
30 58
1 168
250 49
8 192
4 207
11 72
2 129
1 256
21 182
5 245
14 207
8 98
6 2...

output:

803611561

result:

ok answer is 803611561

Test #15:

score: 0
Accepted
time: 2ms
memory: 9776kb

input:

5
654967380 4
49396 4
9666655 4
686820914 0
242360 4

output:

554527316

result:

ok answer is 554527316

Test #16:

score: 0
Accepted
time: 12ms
memory: 201076kb

input:

274
676752 247
8 43
73 271
1595 179
8983 180
23 79
6 271
2 57
1 246
8535035 162
5 179
10 245
9 76
6961 189
5 84
9 242
1093 15
2288 179
8 189
97 194
60 246
213 146
49 111
9 222
6 76
7 180
7 57
9 274
1 180
20730 242
154 242
9311915 246
83 179
611 189
67 57
5322 245
4 111
546 179
4 225
36 246
94163 189...

output:

179763792

result:

ok answer is 179763792

Test #17:

score: 0
Accepted
time: 1ms
memory: 83088kb

input:

110
133 4
8 6
354 105
27981 43
8 47
10 105
7871 36
2 46
1 25
5 44
95 78
4732 76
84 95
18 93
74 10
4 29
15684 98
10 104
8 22
6 85
8747 86
198 0
28 13
70563 103
440 85
32 78
54 25
6 85
7 47
10 80
5 32
176 42
1 70
238 22
80432 11
91 25
8068 43
2 19
10 110
475915 24
8381192 86
7 22
36 28
60 41
142 19
36...

output:

885428573

result:

ok answer is 885428573

Test #18:

score: 0
Accepted
time: 16ms
memory: 174436kb

input:

230
58159529 30
9769810 201
21914014 195
409053382 198
80517379 213
22369256 34
150477785 222
3792405 46
687587 126
1244420 172
14316428 198
24978 189
9211207 134
50672407 36
783350666 17
973354158 13
15239854 225
21495 61
287337032 168
78454047 3
666930336 214
48228545 205
437903923 65
75996605 208...

output:

931508995

result:

ok answer is 931508995

Test #19:

score: 0
Accepted
time: 20ms
memory: 167508kb

input:

220
474731477 209
79324014 153
45600608 82
95373641 154
24795406 135
378117679 76
47450868 122
816602904 82
10082343 90
87805715 17
286857208 116
92566442 219
417859471 99
83437745 181
159394042 147
274860271 198
41883149 153
72603589 29
5204750 98
629323114 89
741686966 7
80065254 206
84091756 0
69...

output:

970797424

result:

ok answer is 970797424

Test #20:

score: 0
Accepted
time: 7ms
memory: 144052kb

input:

196
2 42
5 100
6165 42
4 151
19 157
8 1
3035732 27
7 34
41 192
40 69
4995 86
2 42
6 42
3330 100
49 157
42 12
66 69
230 1
1 192
10 31
583 12
31 160
69090 127
64 1
1536 34
5625 34
719 42
10 157
47 31
725 192
1 42
5 125
675 42
10 42
2 127
15 31
5 86
204012 69
9 164
3 42
91 1
536717 0
80 42
10 53
6 69
1...

output:

660361866

result:

ok answer is 660361866

Test #21:

score: 0
Accepted
time: 3ms
memory: 80288kb

input:

103
93205937 61
147617352 84
730519650 71
872287 91
49326577 82
23132375 24
7219323 90
63854770 84
480460990 71
54611722 24
467241637 53
10521939 53
961418364 82
243821 91
3465 84
700288 53
209741937 71
8187990 61
936398970 61
86199093 24
9998410 90
69688865 61
418263756 90
9496865 0
811896028 61
83...

output:

288450267

result:

ok answer is 288450267

Test #22:

score: 0
Accepted
time: 24ms
memory: 217132kb

input:

283
701218729 245
811104857 26
50714990 114
276487278 207
398933255 70
218528998 152
38920631 245
40305326 70
6057604 155
200833351 245
421140794 7
374271112 245
200329699 154
73218399 70
275108225 207
551433570 207
451721055 220
7076646 238
16496219 70
623859266 31
922926353 7
389757720 70
89737681...

output:

258917177

result:

ok answer is 258917177

Test #23:

score: 0
Accepted
time: 8ms
memory: 152580kb

input:

203
169886 142
2517357 113
850770033 144
5382700 174
6978396 42
104913 182
94199757 182
432388245 30
2756783 144
699537 193
66832822 42
2794264 142
911825087 182
9659793 107
864153 142
772898516 34
715055935 42
97691153 107
37887322 42
661532043 193
79955565 113
269652416 42
8237767 142
3476426 144
...

output:

21037491

result:

ok answer is 21037491

Test #24:

score: 0
Accepted
time: 32ms
memory: 227924kb

input:

298
581679503 138
850221742 13
357421 186
92866522 197
52659317 104
43859 133
73747485 13
312822568 260
3214668 138
83906306 294
14900930 68
68975895 36
5851611 228
30172093 138
44170 138
937592470 138
341899355 260
30272849 224
377920635 13
8648178 241
509939969 241
970058073 228
78680878 36
291859...

output:

897942159

result:

ok answer is 897942159

Test #25:

score: 0
Accepted
time: 1ms
memory: 86128kb

input:

112
63459 9
9 100
95 91
53 31
7 85
457395 100
155014 102
8 24
1 92
413 25
50 27
540 84
8 2
1 61
36 35
9985 3
83348 74
7 45
42914988 65
9 31
2 108
57 78
8 98
54 4
7 57
1747 48
9616 68
935 60
27 73
7 4
3167 91
45 109
64 56
3 86
3 95
13145 18
39 18
1 6
16 84
7409 41
72 56
827 58
540 30
889 18
70 95
15 ...

output:

271481022

result:

ok answer is 271481022

Test #26:

score: 0
Accepted
time: 4ms
memory: 216680kb

input:

300
10 145
5 189
86 197
3 250
883 24
8 250
3 269
254 250
41 271
9903 173
10 210
43 271
881124 271
45 72
53 145
6 145
739 20
59 249
4 280
3557 271
84 266
40 249
6 183
1 271
6 37
46 271
23 265
2 44
834061 189
63 20
466 250
991 169
94 249
726 169
2 20
56000 271
7 271
2 250
62 271
4 144
13399 148
53 24
...

output:

361788157

result:

ok answer is 361788157

Test #27:

score: 0
Accepted
time: 32ms
memory: 230068kb

input:

300
213673503 24
752968248 157
353980 24
2146534 65
79981043 159
495369934 159
298819233 159
536693846 296
791281151 252
873549780 94
849557277 128
733538685 1
231532402 128
634844147 180
962360610 24
677381216 128
650270835 180
860050194 89
5681181 265
709457508 24
311783494 179
772888507 24
135374...

output:

473024736

result:

ok answer is 473024736

Test #28:

score: 0
Accepted
time: 8ms
memory: 223000kb

input:

300
8 262
8 274
9 13
5 271
3 112
8 155
6 146
7 296
9 261
8 195
72 79
76 130
3 258
717 16
14 113
2 30
2 148
7 199
568 47
6 198
90 47
49 176
3 208
7 129
19 221
62 228
77 111
75 252
5 9
4 82
2 230
10 69
34 261
5 233
9 17
3 85
8 250
9 220
5 294
36 5
10 205
9 249
5 15
8 109
6 243
8 195
8 247
10 129
7 277...

output:

129294729

result:

ok answer is 129294729

Test #29:

score: 0
Accepted
time: 24ms
memory: 229136kb

input:

300
97201703 256
42882403 135
559001946 163
462691683 292
669581669 71
392185975 264
340792895 256
781722174 300
88859688 91
508649 272
135981724 199
6833004 290
218519071 229
8782626 47
15175354 141
694551005 174
514923158 25
64136834 78
769078037 96
616546724 36
929337806 24
2676097 173
73621383 2...

output:

139611540

result:

ok answer is 139611540

Test #30:

score: 0
Accepted
time: 64ms
memory: 229988kb

input:

300
934290541 193
719681020 140
639294481 200
372656791 283
442477752 160
26553133 59
291681525 285
30394989 103
148242605 179
830195558 174
96877745 233
409728652 200
782044696 104
102828931 207
477773446 122
6362178 65
193246899 228
816314660 22
13020857 178
882284536 100
933967405 236
49511616 19...

output:

619330717

result:

ok answer is 619330717

Test #31:

score: 0
Accepted
time: 4ms
memory: 212964kb

input:

300
7 66
10 4
5 246
62 156
4 131
2305 137
3 270
4 156
22 156
3 270
6 156
6 66
6 156
90 270
925 156
85 270
2 270
7 11
357 270
3 156
96 66
4 137
58 102
10 270
783 4
9 156
10 102
819 156
8 102
10 194
80720 270
4 66
50 156
5 246
2 156
8 246
4 204
2 270
4 246
243 156
1 156
2 156
70 66
521 66
17 298
65 28...

output:

529082075

result:

ok answer is 529082075

Test #32:

score: 0
Accepted
time: 8ms
memory: 216836kb

input:

300
7 103
970 58
535 205
49 300
43 56
92 167
10 24
7 249
2573 24
4 20
10 202
5 115
9 246
10 38
10 286
4 209
3 139
5 74
3 238
2 181
730 78
4 289
68 265
9 77
7 9
4 262
31 218
6 204
5 44
3 242
86 68
16 185
5 218
7 86
5 1
1 69
8 181
9 160
2 274
1 175
6 157
7 121
18 210
9 297
1 26
1 200
2 291
3 208
29 13...

output:

12351004

result:

ok answer is 12351004

Test #33:

score: 0
Accepted
time: 33ms
memory: 230096kb

input:

300
662810255 55
39403570 188
148464492 40
449036229 245
493336 15
375524580 268
650983681 14
185367364 80
44493118 33
154875055 151
92793465 257
859227729 25
684628954 11
312905823 232
733109524 16
223865635 33
13852846 189
1070161 291
43843425 268
518998752 170
617927854 190
767720166 17
965688640...

output:

590073722

result:

ok answer is 590073722

Test #34:

score: 0
Accepted
time: 43ms
memory: 229372kb

input:

300
728128880 22
120773057 258
77977621 158
637341750 66
828731338 254
216969843 242
28538055 49
3291773 92
59890903 269
872153667 129
719764 211
129710023 233
815145886 295
992973 109
463093811 190
81377363 226
63853219 109
6016163 272
366348 84
853403 207
416004466 297
2646267 98
467102552 39
6839...

output:

253244432

result:

ok answer is 253244432

Test #35:

score: 0
Accepted
time: 30ms
memory: 228932kb

input:

300
583062152 73
934801743 94
165760183 129
927599770 183
37515297 112
15484585 285
868232507 73
95612867 258
480764318 129
220722985 258
981048992 258
51984066 258
542481528 94
526413047 33
36125713 8
8615407 258
205725283 73
72176490 112
903518227 129
934000109 258
518968528 285
801841254 258
4096...

output:

619181538

result:

ok answer is 619181538

Test #36:

score: 0
Accepted
time: 41ms
memory: 229368kb

input:

300
7559583 82
584899424 286
918906481 240
57837566 67
234237154 104
55394161 125
827605997 216
44131533 232
659359012 69
935808295 5
120777841 267
80624325 91
35890284 196
74762705 199
943637737 156
511319458 14
276008796 214
82944668 59
628010630 29
8123164 254
31361177 24
765595174 229
12490585 6...

output:

3822416

result:

ok answer is 3822416

Test #37:

score: 0
Accepted
time: 8ms
memory: 211816kb

input:

300
20 262
7 103
94 103
49 43
4 103
83 38
18223 226
28 10
4 49
10 49
4 103
8 49
4 97
2 38
4 297
6 17
7 49
688 254
77 49
10 38
21 63
22 87
1 275
7 79
52 125
758 261
5 72
569 97
3713 61
9 297
68 103
9803 213
2 118
118 49
6340 49
69 49
8 297
9672 49
6 49
10 17
3 87
2748 49
363 297
3 49
60 297
732 213
9...

output:

164274082

result:

ok answer is 164274082

Test #38:

score: 0
Accepted
time: 8ms
memory: 228960kb

input:

300
620998263 290
8587185 190
686262016 187
46672236 187
115254893 153
752966864 153
80687558 177
116219693 263
199907240 11
943995677 113
50021832 187
977237590 46
87638533 186
43004492 187
591043118 186
398064066 11
853811735 273
473264896 278
22521901 278
818594243 278
283755595 187
877245375 186...

output:

506545062

result:

ok answer is 506545062

Test #39:

score: 0
Accepted
time: 23ms
memory: 217500kb

input:

300
381 245
329 237
5 193
5 237
9 81
222099 237
9485 288
8 237
45 20
68 237
1806 144
742536 237
34 35
5972 237
105 237
4885 237
614 10
1 10
2498017 237
8469 237
142 10
3 282
3 193
1 28
1715 237
56091 10
955859 237
3 237
262 30
4018449 237
1 66
3 99
17997 238
34 237
8 237
9713929 193
8201 193
43386 1...

output:

23033075

result:

ok answer is 23033075

Test #40:

score: 0
Accepted
time: 19ms
memory: 229392kb

input:

300
156535 220
5914550 142
2354121 153
11114973 220
994576940 103
482907881 220
575062186 110
741082750 103
845505717 151
398308403 220
930014687 103
14580524 103
38213803 103
944701416 231
666984091 178
54213289 103
4113906 103
595909233 8
27141155 247
36168465 103
53844404 220
419035469 247
394022...

output:

248430830

result:

ok answer is 248430830

Test #41:

score: 0
Accepted
time: 43ms
memory: 229460kb

input:

300
643300871 11
204237171 6
736677915 26
42094982 91
409274092 141
27574840 159
214051817 29
932300410 16
266984118 293
498551908 238
401269236 59
447127745 75
32878352 226
405137836 185
714930771 250
366931504 98
991098572 44
47168572 289
53352083 265
275404530 150
31855907 74
532600196 299
477660...

output:

16173809

result:

ok answer is 16173809

Test #42:

score: 0
Accepted
time: 47ms
memory: 231344kb

input:

300
998401128 159
57706710 221
318831469 181
64683635 45
1907082 40
31794974 266
2244024 186
14289289 222
425668 53
652277227 118
84806151 73
1394186 121
62805405 117
304770392 132
81471937 70
3072669 280
6760 253
46239 184
459757458 171
700957 132
81477076 150
851421 277
421062 177
611987760 102
12...

output:

660231098

result:

ok answer is 660231098

Test #43:

score: 0
Accepted
time: 15ms
memory: 228752kb

input:

300
398240966 282
880167086 151
785352032 151
586875648 2
448223524 160
989993203 3
599055015 151
200794761 138
515495730 126
776246687 282
581820656 87
437084811 51
399512640 285
128491824 51
579404074 156
313624570 282
263867762 298
412537377 51
328848326 97
90058125 145
222807875 298
675203123 51...

output:

393586578

result:

ok answer is 393586578

Test #44:

score: 0
Accepted
time: 3ms
memory: 217840kb

input:

300
3 238
37 299
37 94
7 280
9 62
71 56
13 53
4 133
10 173
58 290
8 104
3 129
99 1
7 123
7 63
9 280
8 27
2 246
6 4
2 264
36 292
10 100
843 250
1 171
8 46
7 72
2 255
5 106
7 214
10 162
230 57
10 233
6 260
5 267
40 232
10 267
3954 217
6 44
7 253
5 62
90 25
1 275
3 37
30 171
3 57
6 184
33 63
6 57
10 57...

output:

494178031

result:

ok answer is 494178031

Test #45:

score: 0
Accepted
time: 49ms
memory: 229852kb

input:

300
15732293 272
423226269 37
964578301 66
162864956 193
45950269 72
740962260 296
681350005 20
446417008 123
563955786 75
118001920 156
244248029 17
524639103 271
741065682 71
442375202 102
76577988 83
216660833 116
919384432 152
42966431 44
104097605 300
520144706 234
13227140 60
16092208 262
8311...

output:

410376645

result:

ok answer is 410376645

Test #46:

score: 0
Accepted
time: 28ms
memory: 226484kb

input:

300
72 162
7 162
3013 175
894916 97
5129 162
95393743 45
34510 245
512 264
447 264
621 245
7 92
9 50
9679201 162
88134 162
3817 97
27 92
2308 97
41 245
894 264
4819995 265
6013365 162
3 162
5420 162
6397 162
5 162
587 224
54732 162
2 162
7225699 162
9 118
6206872 175
13 162
5 92
6630 160
461541 160
...

output:

436220834

result:

ok answer is 436220834

Test #47:

score: 0
Accepted
time: 4ms
memory: 230992kb

input:

300
5 46
6 167
2 60
8 38
55 27
90 152
6 232
10 191
1 69
3 188
1 9
73 291
8 42
732 219
7 147
6 127
30 6
8 125
27 106
6 226
2 262
69 161
7 126
9 129
10 283
8 96
5 41
2 45
75 299
5 178
8 51
5 94
9 4
1 243
8 277
8 110
5 298
88 60
5 188
6 259
10 211
6 124
6 139
8 39
6 206
1 29
4 87
10 122
3 172
4 192
62 ...

output:

473809216

result:

ok answer is 473809216

Test #48:

score: 0
Accepted
time: 53ms
memory: 228388kb

input:

300
722688130 179
230756118 76
579055804 290
58427998 179
777606179 35
11143043 35
571692997 179
468332850 35
70131373 229
7123518 76
63616857 274
722891112 35
23830970 179
88747992 229
703193029 266
996443258 264
157867639 266
393174156 264
61973327 220
19076270 276
399679608 179
8087678 266
611723...

output:

494185892

result:

ok answer is 494185892

Test #49:

score: 0
Accepted
time: 1ms
memory: 215516kb

input:

300
3 38
36 97
65 279
33 142
10 234
100 38
10 279
92 97
10 279
1 219
7 38
9 160
7 41
5 97
58 279
727 279
99 120
60 279
4 41
10 219
7 142
1 41
9 279
9 97
7 38
83 279
9 219
3 282
8 279
3 120
34 267
15 26
5 97
3 97
4 234
8 161
6 276
84 279
6 169
6 26
5 279
8 120
6 9
1 143
10 279
1 38
7 279
79 219
66 27...

output:

771026146

result:

ok answer is 771026146

Test #50:

score: 0
Accepted
time: 12ms
memory: 230904kb

input:

300
452384262 230
792237885 18
808914789 230
104642499 230
235601526 167
875195335 90
405007000 236
781658742 167
370440520 178
36896239 230
787874395 230
40403482 230
111408719 230
836830204 56
382145077 127
308659541 208
3642213 208
15648389 230
904139781 230
693699597 73
13172390 127
59974654 56
...

output:

360460036

result:

ok answer is 360460036