QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153265#7078. Tower of the SorcererPetroTarnavskyiAC ✓3136ms10080kbC++172.7kb2023-08-29 19:42:042023-08-29 19:42:04

Judging History

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

  • [2023-08-29 19:42:04]
  • 评测
  • 测评结果:AC
  • 用时:3136ms
  • 内存:10080kb
  • [2023-08-29 19:42:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))

#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int INF = 1000'000'447;
const LL LINF = 1ll * INF * INF;

const int MAX = 1 << 19;

LL t[MAX];
	
struct Segtree
{
	int n;
	
	void init(int nn)
	{
		n = 1;
		while (n < nn) n *= 2;
		FOR (i, 0, 2 * n) t[i] = LINF;
	}
	
	LL mn(int v, int tl, int tr, int l, int r)
	{
		if (l <= tl && tr <= r)
			return t[v];
		if (l >= tr || tl >= r)
			return LINF;
		int m = (tl + tr) / 2;
		LL ans = LINF;
		if (l < m)
			ans = min(ans, mn(v * 2, tl, m, l, r));
		if (r > m)
			ans = min(ans, mn(v * 2 + 1, m, tr, l, r));
		return ans;
	}
	
	LL mn(int l, int r)
	{
		return mn(1, 0, n, l, r);
	}
	
	void change(int v, int l, int r, int i, LL x)
	{
		if (l + 1 == r)
		{
			t[v] = x;
			return;
		}
		int m = (l + r) / 2;
		if (i < m)
			change(v * 2, l, m, i, x);
		else
			change(v * 2 + 1, m, r, i, x);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
	
	void change(int i, LL x)
	{
		change(1, 0, n, i, x);
	}
};

const int N = 1e5 + 47;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, d;
	cin >> n >> d;
	
	Segtree st;
	st.init(n + 1);
	
	vector<PII> a(n);
	int mx = d;
	FOR (i, 0, n)
	{
		cin >> a[i].F >> a[i].S;
		mx = max(mx, a[i].F);
	}
	
	a.PB({d, 0});
	sort(ALL(a));
	int b = lower_bound(ALL(a), MP(d, 0)) - a.begin();
	n++;
		
	vector<LL> pref(n + 1);
	FOR (i, 0, n)
	{
		LL val = (a[i].S - 1) / mx * a[i].F;
		pref[i + 1] = pref[i] + val;
	}
	vector<LL> dp(n, LINF);
	
	
	//FOR (i, b + 1, n)
	//{
	//	if (a[i].S <= d)
	//	{
	//		d = a[i].F;
	//		b = i;
	//	}
	//}
	
	dp[b] = pref[b];
	st.change(b, pref[b] - pref[b + 1]);
	
	VI R(N);
	FOR (j, 0, N)
	{
		R[j] = lower_bound(ALL(a), MP(j, -1)) - a.begin();
	}
	
	FOR (i, b + 1, n)
	{
		int x = 1;
		int l = lower_bound(ALL(a), MP(x, -1)) - a.begin();
		int hp = a[i].S - 1;
		while (x <= hp)
		{
			int k = hp / x;
			LL q = LL(k) * a[i].F;
			int nx = hp / k;
			int r = R[nx + 1];
			dp[i] = min(dp[i], pref[i] + st.mn(l, r) + q);
			x = nx + 1;
			l = r;
			if (r >= i) break;
		}
		int r = n;
		dp[i] = min(dp[i], pref[i] + st.mn(l, r));
		st.change(i, dp[i] - pref[i + 1]);
		//if (a[i].F >= a[n - 1].S && i != n - 1) i = n - 2; 
	}
	cout << dp[n - 1] << '\n';

	cerr << db(clock()) / CLOCKS_PER_SEC << '\n';
	
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

4 1
3 2
4 4
5 6
1 6

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 59ms
memory: 6052kb

input:

5000 679
84191 46042
81916 66659
74636 72443
10252 57443
21838 54620
84896 58466
20832 29643
45949 20576
50399 51434
56472 90759
68909 94348
39459 1731
81207 17614
26465 11775
93861 24936
25017 64663
21042 37570
32903 68583
68840 58347
93849 10841
10190 77131
10595 1959
57163 59047
16066 89850
73741...

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 58ms
memory: 4164kb

input:

5000 685
67283 21828
19841 367
69908 57925
63894 10753
20139 20595
672 47788
81010 57483
53755 96758
85049 78636
94198 12795
97299 86489
57399 56590
30519 63514
92072 5714
60572 8651
25620 13514
27482 51652
88352 27272
4391 23458
43759 57471
95084 88191
53782 96875
52546 33731
95458 5643
75049 42685...

output:

60515

result:

ok single line: '60515'

Test #4:

score: 0
Accepted
time: 56ms
memory: 4148kb

input:

5000 883
57988 4889
27548 3497
47774 97848
73725 83535
43075 12741
86312 87522
98386 29435
88105 19813
50656 83340
32721 37465
84421 14671
92169 37187
33163 53370
95155 35577
63396 86337
20931 57282
80964 12797
84905 95122
7530 7623
1393 58436
9609 91063
92309 31959
37789 98189
74209 33091
64400 530...

output:

142420

result:

ok single line: '142420'

Test #5:

score: 0
Accepted
time: 58ms
memory: 4204kb

input:

5000 110
81857 71124
57698 64343
80952 96284
15190 95432
51153 64223
39943 25603
77013 72711
94708 24951
64786 9225
54307 29867
2166 9420
38155 28813
96118 90751
85381 30858
17457 43971
38450 20480
36831 31955
86436 3116
71718 45322
2141 92627
36585 66945
8885 99790
49929 5604
25126 14766
78673 4804...

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 51ms
memory: 4116kb

input:

5000 852
68512 97389
60972 88659
73325 90709
87906 83485
39089 40758
25295 95321
61154 18959
19137 97232
40721 17563
3359 33010
484 29851
3964 60841
88065 81476
1622 35273
28703 97697
72577 9099
16043 92977
37261 95232
41086 16776
38139 94039
79650 24363
30987 95332
81397 67793
52508 71034
22631 725...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 81ms
memory: 4148kb

input:

5000 23
49957 100000
97978 100000
66997 100000
70406 100000
62250 100000
71093 100000
14758 100000
59859 100000
81605 100000
50139 100000
97303 100000
23626 100000
38523 100000
5028 100000
59461 100000
99559 100000
5150 100000
21343 100000
5738 100000
81487 100000
87427 100000
67101 100000
8692 1000...

output:

251733189

result:

ok single line: '251733189'

Test #8:

score: 0
Accepted
time: 52ms
memory: 4196kb

input:

5000 10
100000 64460
100000 96604
100000 64490
100000 95985
100000 52966
100000 9407
100000 2618
100000 50047
100000 37993
100000 94354
100000 47586
100000 91096
100000 18738
100000 88600
100000 37646
100000 88124
100000 43502
100000 56950
100000 81193
100000 14352
100000 54736
100000 14837
100000 1...

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 75ms
memory: 4156kb

input:

5000 51
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 10000...

output:

196000000

result:

ok single line: '196000000'

Test #10:

score: 0
Accepted
time: 9ms
memory: 4176kb

input:

5000 2
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 24...

output:

11807600

result:

ok single line: '11807600'

Test #11:

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

input:

5000 11
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 10...

output:

45450000

result:

ok single line: '45450000'

Test #12:

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

input:

2 1
1 100000
100000 1

output:

0

result:

ok single line: '0'

Test #13:

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

input:

2 1
1 3
3 100

output:

297

result:

ok single line: '297'

Test #14:

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

input:

100 178
157 16066
189 16201
134 18255
190 12359
142 15665
192 17956
120 14861
194 18445
169 13814
190 10523
198 11396
188 13529
164 16559
138 13158
154 13246
123 12920
190 19092
181 19819
147 18071
188 11408
134 17172
148 14664
192 17871
143 18116
109 19693
179 12343
180 17090
150 12711
200 19798
17...

output:

1168450

result:

ok single line: '1168450'

Test #15:

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

input:

100 9236
7864 75108
8699 16535
376 50738
5639 97958
1784 75293
9729 88266
8655 81610
9938 74490
8566 17220
9666 21635
8362 43274
1995 15239
3613 63840
8632 64439
2242 12081
3354 13214
2507 81554
7578 31837
9960 13140
1185 18627
8361 27567
3592 45065
5251 40472
9311 31355
5034 65035
5613 74538
6905 2...

output:

2511795

result:

ok single line: '2511795'

Test #16:

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

input:

100 4368
5639 95168
7156 47518
8137 57053
1704 48642
3005 91592
7450 64182
3425 38836
5516 77818
7703 67882
8744 42240
1318 42471
6684 39471
5381 43548
1742 67073
1030 70989
2157 15781
3176 51219
6351 36894
4604 5818
9460 39265
5931 90339
7116 37275
8648 16323
9825 10441
8072 42787
9503 68159
7434 9...

output:

2538739

result:

ok single line: '2538739'

Test #17:

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

input:

100 259
80 62302
302 57717
193 13269
771 58062
219 26436
554 22639
108 77948
970 89532
447 19679
760 97544
48 44667
211 94414
610 96029
527 37537
17 61669
995 86153
168 57342
987 11576
693 20776
174 55470
168 71708
681 10275
432 22361
106 80512
853 31365
845 57897
207 37804
107 15058
662 26829
30 57...

output:

2565739

result:

ok single line: '2565739'

Test #18:

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

input:

100 94765
44791 9234
39635 44708
39512 84352
32154 66011
95490 38673
69605 76862
27992 84300
90563 32269
13845 16554
22423 62907
50980 71481
21655 7696
96806 72538
12431 84328
93712 11554
44475 91283
7050 94813
29168 64499
24721 33319
80563 34144
28949 60657
3264 38471
86940 51106
26629 76327
87933 ...

output:

0

result:

ok single line: '0'

Test #19:

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

input:

1000 195
187 11608
136 14918
135 15113
159 11782
159 13355
151 14945
103 14301
153 11918
187 15797
159 15577
175 16979
178 15105
132 17688
160 11025
145 13008
176 14603
166 15739
116 18242
194 19461
117 18584
104 19047
142 12937
128 14092
158 15208
146 12487
197 17821
138 19564
150 11753
142 18718
1...

output:

11220118

result:

ok single line: '11220118'

Test #20:

score: 0
Accepted
time: 5ms
memory: 3952kb

input:

1000 3689
2418 25992
2569 90297
1939 65017
2894 50479
3342 93448
601 95293
126 34177
2683 14222
3692 55360
4435 70569
2233 15930
2285 94214
1696 48218
2605 18093
264 70767
2177 87976
3069 38238
3128 13627
2069 95572
664 31911
1153 38299
2847 18232
663 94897
526 61842
3458 36552
1804 43399
3010 18977...

output:

26297784

result:

ok single line: '26297784'

Test #21:

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

input:

1000 3308
1336 99208
2118 65085
1307 44413
602 84005
4354 55223
721 54826
3699 58727
1247 99323
4329 93508
2854 69922
3612 84741
4387 35136
3016 74005
807 37010
2316 82232
2184 97191
4810 33549
2994 67161
3423 89070
3359 21907
2994 90806
4974 84031
3994 66716
2170 62740
1393 77560
4841 54589
2048 49...

output:

27618897

result:

ok single line: '27618897'

Test #22:

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

input:

1000 5690
5272 18563
2208 13185
9929 714
6120 93411
4027 65417
3274 6417
1557 15728
6169 20252
7863 64435
9467 7163
6526 52042
8295 47015
2836 21585
2188 76447
7822 43273
4361 76646
3978 12213
8282 55488
1772 69598
1097 68665
4831 22992
2052 25566
6487 25818
5874 87873
6847 87090
6630 15385
3127 178...

output:

25274270

result:

ok single line: '25274270'

Test #23:

score: 0
Accepted
time: 6ms
memory: 3820kb

input:

1000 613
622 12278
294 36627
327 50583
79 54719
527 64809
242 20366
611 71052
924 86998
685 68548
586 42802
289 60911
299 23970
761 69745
362 21439
354 57080
205 25072
197 73906
601 17218
511 26906
699 69989
777 51114
128 20489
848 21377
486 17410
582 61455
649 53973
423 62451
55 44187
854 75577
444...

output:

26928349

result:

ok single line: '26928349'

Test #24:

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

input:

1000 9061
4223 28214
1308 25048
2247 9513
5616 51812
1155 29478
6145 51360
1187 96078
6523 91752
9627 68567
2715 5130
9317 88298
9572 94956
2317 16166
4076 28740
7715 1500
2191 62367
9053 31921
4699 12987
3378 52095
6867 7340
8256 79347
4317 96091
1446 22865
1124 34274
5819 7116
3126 49745
2837 9431...

output:

22397306

result:

ok single line: '22397306'

Test #25:

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

input:

1000 93761
13042 45072
30325 40700
72475 32486
18918 54911
83363 66278
43430 12654
35635 60291
67455 81519
88983 64792
18976 18541
26303 98722
20826 7192
4350 6177
47363 92867
3086 45596
49463 11493
59403 42842
47058 13305
43315 63433
68535 28670
1452 50266
60108 4919
75230 80419
11932 85707
73877 1...

output:

0

result:

ok single line: '0'

Test #26:

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

input:

100000 1
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 1...

output:

9999900000

result:

ok single line: '9999900000'

Test #27:

score: 0
Accepted
time: 1733ms
memory: 9456kb

input:

100000 5366
6038 69255
8540 48771
2631 16671
2625 88929
8795 19689
8448 52309
6055 95769
5753 72461
3730 59096
59 70102
2184 36567
2254 69073
4872 93717
4346 25005
9926 64985
9678 50911
9273 82452
970 86394
7054 58076
4149 79485
4403 39607
9687 39308
7645 22272
7968 62643
147 30008
1376 88513
1392 6...

output:

2495521379

result:

ok single line: '2495521379'

Test #28:

score: 0
Accepted
time: 305ms
memory: 8796kb

input:

100000 9162
3148 54400
9181 29282
1661 97797
4031 30927
2169 30632
9412 87441
4643 41590
6022 25087
1247 63915
3077 73152
3736 45532
5477 92817
5323 20495
9038 9538
1354 32542
8571 96409
4491 5912
892 40717
5287 53600
9892 51820
2235 99724
2715 95797
2730 5447
156 62207
5288 20143
8520 43505
6785 62...

output:

2252325798

result:

ok single line: '2252325798'

Test #29:

score: 0
Accepted
time: 2536ms
memory: 9680kb

input:

100000 413
62258 91519
77692 62992
19764 26696
70685 57191
44108 80949
78663 87882
87439 72112
89312 40742
16407 32647
38420 30443
99936 3693
41649 13102
73452 79096
45931 7205
22880 82177
79577 10382
12005 19399
66870 86632
49448 55500
89601 75319
12538 62070
85405 34980
87536 43183
60850 48987
408...

output:

0

result:

ok single line: '0'

Test #30:

score: 0
Accepted
time: 37ms
memory: 8924kb

input:

100000 197
159 16368
100 10619
106 15521
103 11334
176 14602
200 18010
199 16873
182 15955
181 13568
172 11421
145 16950
124 12861
122 19502
161 16840
185 18800
173 10792
184 10986
197 17229
182 14548
100 10461
166 12290
120 12164
116 17035
117 16267
152 15607
193 12663
143 15273
138 18904
182 10050...

output:

1116803442

result:

ok single line: '1116803442'

Test #31:

score: 0
Accepted
time: 976ms
memory: 8844kb

input:

100000 3859
4649 87809
1455 83124
2284 69307
1946 69796
4079 87056
4973 89936
2404 84729
4479 88825
2649 80269
1761 57798
2548 96884
4737 86626
3337 97219
1163 67127
3617 80139
2006 75798
658 56431
4414 74582
1170 62616
2296 65879
1912 66496
1767 79378
1772 63468
1092 60832
682 81539
4772 98155
3447...

output:

3703465469

result:

ok single line: '3703465469'

Test #32:

score: 0
Accepted
time: 675ms
memory: 9468kb

input:

100000 2754
2907 87567
1201 71345
3299 55204
4076 59219
4159 53409
4836 97458
1239 70072
3563 93313
1791 52735
2181 94352
2074 72161
2686 75190
4454 91989
1794 88056
3509 83003
3096 90944
2817 83086
1092 51597
3322 91495
4302 93333
1203 98575
3189 98489
4441 78134
4515 78280
1216 63470
2723 94238
29...

output:

4355475875

result:

ok single line: '4355475875'

Test #33:

score: 0
Accepted
time: 316ms
memory: 9244kb

input:

100000 7132
9531 33225
9306 27770
1962 52481
6227 54156
5154 650
5813 90925
6151 70289
3505 47676
2764 26983
2709 23900
7052 29761
5922 91925
6916 20153
7987 4753
3754 6091
1140 29248
9468 32025
3538 28916
2289 14856
1941 79750
4950 48289
6956 5167
1535 74737
2561 30640
7292 82985
9055 61515
2128 58...

output:

2470997022

result:

ok single line: '2470997022'

Test #34:

score: 0
Accepted
time: 1886ms
memory: 8028kb

input:

100000 171
469 23603
394 78629
915 29373
904 63889
500 19635
884 84052
987 69429
460 45796
787 60687
724 46478
189 70890
767 99228
309 42789
696 89808
474 75431
981 56728
465 54615
914 86212
852 81795
576 24440
973 88191
419 37358
543 58921
797 40546
932 81176
929 43645
704 80888
647 98649
994 12567...

output:

2989584437

result:

ok single line: '2989584437'

Test #35:

score: 0
Accepted
time: 2341ms
memory: 8412kb

input:

100000 300
416 11319
1803 13825
1629 3058
950 94097
1614 90693
1272 93262
966 8953
1378 71183
1622 94797
367 76314
1237 34293
892 55182
693 12727
282 64314
1808 91948
1322 5059
738 11685
266 82658
1329 68228
187 74564
1033 98654
1550 73576
675 44096
1440 21892
1882 49671
1820 74625
441 84550
1103 19...

output:

2566613627

result:

ok single line: '2566613627'

Test #36:

score: 0
Accepted
time: 31ms
memory: 9832kb

input:

100000 1984
777 83581
1862 89453
714 7870
1698 55799
1979 16598
751 68163
1878 93735
1447 40638
1438 91403
1097 24812
1735 95791
1860 43748
1315 99955
996 11599
1769 33675
1384 63053
1459 28545
964 65935
1320 22384
1715 96286
674 60682
1732 62867
948 34868
1130 12221
1073 21765
691 63102
1072 69674
...

output:

3065972699

result:

ok single line: '3065972699'

Test #37:

score: 0
Accepted
time: 490ms
memory: 8588kb

input:

100000 1077
1193 50551
1392 999
1075 91049
1443 86982
1031 65494
1753 8905
1067 11883
1185 47298
1505 81626
1189 91139
1174 35770
1032 75846
1351 57220
1234 36614
1883 31960
1907 61060
1338 50262
1681 72483
1005 83974
1017 72907
1301 54192
1291 35306
1297 24965
1197 57166
1408 88084
1775 90636
1476 ...

output:

3673470839

result:

ok single line: '3673470839'

Test #38:

score: 0
Accepted
time: 297ms
memory: 8284kb

input:

100000 1138
260 2486
781 2390
1635 8533
1532 6497
1448 8064
1536 405
365 8625
1133 9676
820 9477
1386 9143
1903 174
1673 6329
1603 6800
1079 8903
368 9780
436 7358
1612 1783
1636 61
606 620
163 3590
550 4038
1001 898
1818 7807
1694 6842
569 7285
1559 4478
879 3751
1304 9602
1386 476
1445 4172
1499 7...

output:

209690519

result:

ok single line: '209690519'

Test #39:

score: 0
Accepted
time: 291ms
memory: 10080kb

input:

100000 1431
1392 10443
1475 11682
894 29436
795 20635
1236 11619
1812 4857
1077 25197
505 3002
616 13692
1019 16465
1044 34467
1889 23094
711 25229
755 5331
707 20967
1985 41640
1837 30386
1288 33351
698 3186
1233 28280
1069 33985
1782 13703
1550 5628
1184 26689
915 15893
1147 10971
766 10735
1063 7...

output:

1496066026

result:

ok single line: '1496066026'

Test #40:

score: 0
Accepted
time: 1010ms
memory: 8040kb

input:

100000 579
1994 12440
1191 12117
111 13146
1286 14817
1289 10501
1516 13489
966 15819
478 17389
1855 11489
1829 18938
1585 18989
147 16362
1817 17819
1177 15591
267 15367
117 16136
813 18830
1079 11152
435 12656
1013 18163
351 12875
1800 10670
1983 16923
1844 13209
1830 11083
1229 12688
465 10184
19...

output:

737690029

result:

ok single line: '737690029'

Test #41:

score: 0
Accepted
time: 137ms
memory: 8392kb

input:

100000 1637
780 19924
1530 13482
1355 18046
1182 10985
935 11544
664 13059
1903 18817
1345 19154
1219 18270
787 13141
1532 18336
1333 17137
1519 13324
1316 16611
742 18774
1713 15332
635 18808
642 18639
785 11290
902 15639
1913 16882
997 10784
1004 19714
743 19602
1490 18247
1960 13675
1652 16131
96...

output:

875973503

result:

ok single line: '875973503'

Test #42:

score: 0
Accepted
time: 368ms
memory: 8088kb

input:

100000 14
30 98196
41 11637
72 99937
31 29504
96 57779
87 54509
83 74049
37 93645
91 92138
82 37028
39 64493
91 67377
60 26417
35 54741
28 79302
83 62372
79 70858
25 88547
16 63563
45 81466
91 12414
46 91945
89 64038
11 84651
20 68763
24 37020
87 56328
77 58939
17 40379
35 84462
74 38456
82 47747
50...

output:

3030239207

result:

ok single line: '3030239207'

Test #43:

score: 0
Accepted
time: 184ms
memory: 8076kb

input:

100000 467
143 18391
471 22687
231 21806
383 94823
362 46527
451 88115
320 89601
360 92308
383 46466
349 95722
270 60335
126 36990
113 68071
355 58054
203 30398
394 36124
117 17117
269 29509
474 36595
201 70286
167 16541
495 63496
242 75553
235 39044
251 14389
212 10259
351 89496
439 83002
407 26598...

output:

3280331792

result:

ok single line: '3280331792'

Test #44:

score: 0
Accepted
time: 666ms
memory: 8472kb

input:

100000 807
93 37772
697 6428
54 79802
63 70340
768 26414
846 62975
831 31239
260 79562
588 76037
980 61059
860 31552
596 72368
16 62714
168 90817
467 85639
637 25933
239 18782
167 95748
976 80220
659 57835
479 87249
173 29626
864 24676
604 87580
620 77072
241 70459
832 19017
444 61848
325 55889
103 ...

output:

2507577679

result:

ok single line: '2507577679'

Test #45:

score: 0
Accepted
time: 503ms
memory: 9120kb

input:

100000 8603
6807 64172
6688 36616
1288 83080
6713 41220
3546 82426
6960 84171
5732 42734
2389 6745
3471 49441
5180 35727
5658 51888
6367 2124
9289 79096
393 85090
2386 96074
1484 19731
574 98310
9597 58095
9886 12840
5315 32088
1796 17743
9051 98037
2709 9576
3143 1136
4126 93265
9466 45632
4572 401...

output:

2262610643

result:

ok single line: '2262610643'

Test #46:

score: 0
Accepted
time: 2618ms
memory: 9580kb

input:

100000 2485
40357 88472
6643 60386
99285 70965
38756 72126
30751 37879
99757 60186
9346 99560
94017 61365
19073 37307
66259 76312
73764 46265
60383 89749
66357 74679
63168 24842
8228 77181
47191 80694
89444 60946
32427 33738
10955 63403
4451 68868
87094 24155
20302 28091
18338 90208
96219 19193
2504...

output:

31035

result:

ok single line: '31035'

Test #47:

score: 0
Accepted
time: 1826ms
memory: 8988kb

input:

100000 449
121 61674
331 90298
696 77406
156 54152
822 71322
943 97327
190 53972
594 85860
959 51258
957 65394
436 55671
218 50617
973 64040
1000 52747
467 94349
603 60666
847 94403
681 53004
826 69224
430 86702
603 59083
126 85014
833 72278
618 85812
356 84879
637 90518
139 79950
890 87682
929 9326...

output:

4099888809

result:

ok single line: '4099888809'

Test #48:

score: 0
Accepted
time: 2067ms
memory: 9352kb

input:

100000 962
1922 82159
1172 65961
330 72951
916 85257
1084 65186
1694 72909
1814 78576
1736 77301
756 75425
1039 56624
580 56673
1969 97592
733 69136
1439 95827
1313 73882
1594 62465
280 76081
1006 78748
537 71007
342 59695
1398 79066
536 88491
798 64446
156 86674
394 54393
1584 84342
477 52488
760 8...

output:

3882093262

result:

ok single line: '3882093262'

Test #49:

score: 0
Accepted
time: 399ms
memory: 8032kb

input:

100000 42421
24251 31124
2844 62655
37641 1407
26595 3336
5548 84655
19994 38925
34016 60170
14966 58743
29028 3874
48083 45926
18403 11596
29705 47212
10621 5466
23602 51973
27763 98743
13474 7931
25956 53503
7048 27664
42470 95736
32104 1201
14760 62691
48607 87513
26971 63366
45902 23903
6126 679...

output:

1261460150

result:

ok single line: '1261460150'

Test #50:

score: 0
Accepted
time: 3136ms
memory: 9100kb

input:

100000 1785
9350 84598
1278 90260
5082 88623
4259 71511
8955 88184
1353 57952
6877 83911
2945 53648
5297 85512
5266 94069
1565 64104
9210 54058
7454 71590
443 79611
5033 88577
5178 81828
3445 62069
1018 92594
581 62731
8617 76908
3165 75319
6057 86114
2219 84965
1735 63021
2481 71439
348 79152
4737 ...

output:

3543585666

result:

ok single line: '3543585666'

Test #51:

score: 0
Accepted
time: 177ms
memory: 8692kb

input:

100000 878
1795 7620
1120 6852
552 4302
1934 3469
757 2746
1874 7885
986 515
1557 5522
1585 1801
1743 3324
1529 6335
1808 8913
1713 9468
1210 6938
1648 1403
671 2116
1085 1467
1829 4401
1409 399
594 836
1905 9614
904 6457
641 2756
1939 1530
1768 944
1665 6283
774 2884
1228 9647
1069 4008
1126 9504
1...

output:

250073044

result:

ok single line: '250073044'

Test #52:

score: 0
Accepted
time: 973ms
memory: 9120kb

input:

100000 708
714 100000
1151 100000
1693 100000
1380 100000
868 100000
580 100000
975 100000
1587 100000
578 100000
1595 100000
1750 100000
942 100000
1870 100000
928 100000
1490 100000
1151 100000
1937 100000
521 100000
1306 100000
997 100000
1048 100000
1431 100000
1503 100000
1129 100000
1731 10000...

output:

6123919725

result:

ok single line: '6123919725'

Test #53:

score: 0
Accepted
time: 202ms
memory: 8036kb

input:

100000 71
69 45507
83 3132
55 92929
22 71365
100 94282
41 53181
3 87761
79 42968
71 35304
100 92622
9 30171
44 89918
31 73377
22 45123
14 68713
65 83905
77 21039
6 9007
3 84041
20 8698
70 67977
26 2714
94 1962
81 68223
70 49866
84 98476
68 82880
62 76877
24 49152
55 33506
28 96221
71 6737
51 16290
7...

output:

2524559429

result:

ok single line: '2524559429'

Test #54:

score: 0
Accepted
time: 2330ms
memory: 8776kb

input:

100000 126
365 20005
394 39922
240 86273
655 81338
790 59150
574 54823
728 83093
444 66952
540 37432
1 34971
260 47835
912 30981
680 86314
995 11917
344 84447
390 29542
754 13345
928 41745
874 23226
53 66560
685 59487
382 14787
509 67430
470 40578
672 96035
831 24564
345 54011
780 46383
678 71966
26...

output:

2728088417

result:

ok single line: '2728088417'

Test #55:

score: 0
Accepted
time: 2503ms
memory: 9732kb

input:

100000 1782
1395 71576
4857 75620
2410 68200
627 76003
3472 19867
758 28321
2618 87466
1289 48608
2672 53209
3477 70756
1614 15676
1201 10607
2948 73345
31 35717
2263 38125
3148 64663
4541 14743
4563 85029
3245 55591
4403 87500
1557 12748
2941 12391
2970 16703
3159 68649
820 96402
2931 26111
3670 75...

output:

2627578502

result:

ok single line: '2627578502'

Test #56:

score: 0
Accepted
time: 2299ms
memory: 9304kb

input:

100000 9325
40503 28958
21442 85627
24585 21142
41547 30339
13872 35471
35317 96432
9543 69853
8100 86144
37599 80522
29683 3367
39530 4594
24271 1610
41185 21574
40458 22821
32832 90345
27194 4134
12485 470
35047 12495
2756 84983
27152 77304
6661 92911
34743 87338
32020 40402
43632 24901
42913 2221...

output:

1239408620

result:

ok single line: '1239408620'

Test #57:

score: 0
Accepted
time: 629ms
memory: 9364kb

input:

100000 39923
34107 87026
44168 49801
4739 55643
34327 81768
30508 59566
39157 97598
28134 80247
15208 84539
10336 40924
5854 25928
6386 95231
28116 76587
19396 90362
48927 48345
31652 14472
14967 35249
7621 49294
35735 86353
31210 58352
15871 61626
36431 77133
21682 11710
1121 84476
48296 54215
3075...

output:

1382901700

result:

ok single line: '1382901700'

Test #58:

score: 0
Accepted
time: 276ms
memory: 9012kb

input:

100000 46519
20424 67993
13494 62280
11905 70703
34688 83030
10184 73653
28431 92035
35614 62908
9802 72443
16181 58249
26690 91413
566 94142
11173 84338
27389 65808
28492 64570
29688 71387
19294 93683
32379 74229
48522 94175
11358 91545
32946 61982
40973 75851
11850 91474
29384 97928
45949 59156
19...

output:

2498783034

result:

ok single line: '2498783034'

Test #59:

score: 0
Accepted
time: 853ms
memory: 8444kb

input:

100000 34800
9933 100000
31563 100000
2198 100000
1527 100000
38156 100000
25436 100000
17688 100000
5027 100000
21124 100000
26857 100000
27967 100000
5231 100000
31980 100000
7883 100000
25874 100000
34197 100000
25293 100000
39595 100000
41211 100000
40349 100000
40289 100000
47777 100000
41220 1...

output:

2505329659

result:

ok single line: '2505329659'

Test #60:

score: 0
Accepted
time: 1048ms
memory: 8548kb

input:

100000 6501
1538 99468
3940 67286
8224 10951
1315 4666
514 6759
9056 95255
1910 91513
3855 20534
5764 18850
356 33429
2481 82650
8520 88999
5509 40428
7962 88559
5925 43704
1011 40457
6211 66322
3441 28162
4481 87456
5973 20507
2439 99583
8362 89097
2646 25374
9634 6840
4614 53921
1213 78276
7600 61...

output:

2279598856

result:

ok single line: '2279598856'

Test #61:

score: 0
Accepted
time: 266ms
memory: 9264kb

input:

100000 41463
26788 71868
52532 55506
28889 41879
19498 90728
64413 17667
41663 42342
46442 45046
25655 84034
70086 40391
16240 91189
68319 36338
95433 57470
63523 30136
59272 33823
46416 79676
48512 61918
89427 40006
81168 83206
34860 47908
42280 58723
50291 38756
84817 60682
27550 44156
47999 49774...

output:

0

result:

ok single line: '0'

Test #62:

score: 0
Accepted
time: 10ms
memory: 3912kb

input:

1000 1
55725 56643
66764 67975
27701 27214
99831 99840
53750 53991
8508 10335
20030 20723
92983 91472
20398 21235
90848 89079
35601 34001
65119 66074
96142 95385
70410 71831
26540 26306
7146 8743
49174 49954
47933 48524
46693 46657
35522 33997
92693 90988
48218 48652
32976 31634
11452 12068
26625 26...

output:

309995

result:

ok single line: '309995'

Test #63:

score: 0
Accepted
time: 123ms
memory: 4324kb

input:

10000 1
14322 14663
29459 30573
89007 88771
73561 74580
71019 72260
15629 15921
34808 35528
69540 70799
98516 98463
66383 67258
22779 23729
68783 69960
40737 41905
29278 30430
41795 42736
7051 6860
89321 89178
16391 16573
51717 52390
25003 25868
73789 74712
48039 48897
55674 56012
96032 96328
94468 ...

output:

198712

result:

ok single line: '198712'

Test #64:

score: 0
Accepted
time: 1886ms
memory: 8188kb

input:

100000 1
36859 36859
88347 88347
59933 59933
45580 45580
12030 12030
80634 80634
21589 21589
62979 62979
76057 76057
58702 58702
55552 55552
37091 37091
92843 92843
94255 94255
77430 77430
49176 49176
73965 73965
81888 81888
94229 94229
7171 7171
59659 59659
44234 44234
95998 95998
22285 22285
98344...

output:

200005

result:

ok single line: '200005'

Test #65:

score: 0
Accepted
time: 1873ms
memory: 7916kb

input:

100000 10
97710 97710
5988 5988
51602 51602
16298 16298
64202 64202
71992 71992
36783 36783
17337 17337
39723 39723
85016 85016
67336 67336
81734 81734
31802 31802
24389 24389
83013 83013
32845 32845
60646 60646
53468 53468
46932 46932
90479 90479
30749 30749
41395 41395
34022 34022
49460 49460
8135...

output:

199992

result:

ok single line: '199992'

Test #66:

score: 0
Accepted
time: 1863ms
memory: 9296kb

input:

100000 100
87747 87747
30645 30645
63212 63212
2616 2616
62294 62294
80529 80529
18276 18276
50076 50076
24624 24624
97386 97386
69744 69744
99152 99152
32271 32271
98019 98019
77360 77360
49700 49700
11744 11744
79983 79983
43917 43917
1323 1323
43275 43275
62353 62353
65650 65650
27994 27994
17373...

output:

199807

result:

ok single line: '199807'

Test #67:

score: 0
Accepted
time: 1872ms
memory: 9384kb

input:

100000 1000
26706 26706
78357 78357
4678 4678
95682 95682
59529 59529
14129 14129
35488 35488
3628 3628
77754 77754
94610 94610
90372 90372
42935 42935
61807 61807
49618 49618
27544 27544
32928 32928
91065 91065
65335 65335
24811 24811
40122 40122
61137 61137
28661 28661
35054 35054
23926 23926
9043...

output:

198438

result:

ok single line: '198438'

Test #68:

score: 0
Accepted
time: 1794ms
memory: 8888kb

input:

100000 10000
37327 37327
42348 42348
84853 84853
98283 98283
62194 62194
46047 46047
43160 43160
53495 53495
66801 66801
45618 45618
96007 96007
26923 26923
28846 28846
11511 11511
38596 38596
49724 49724
9245 9245
51830 51830
39618 39618
9772 9772
63208 63208
2551 2551
61161 61161
60695 60695
37597...

output:

187500

result:

ok single line: '187500'

Test #69:

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

input:

100000 100000
13761 13761
93673 93673
31753 31753
8576 8576
726 726
58402 58402
86853 86853
69410 69410
78127 78127
7064 7064
49156 49156
44044 44044
58356 58356
27054 27054
69840 69840
3998 3998
23764 23764
71608 71608
22027 22027
39578 39578
31879 31879
77173 77173
55271 55271
99686 99686
31279 31...

output:

0

result:

ok single line: '0'