QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43734#2021. 有源汇有上下界最小费用最大流(随机数据)sd03AC ✓2059ms6184kbC++203.3kb2022-08-10 15:41:262022-08-10 15:41:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-10 15:41:26]
  • 评测
  • 测评结果:AC
  • 用时:2059ms
  • 内存:6184kb
  • [2022-08-10 15:41:26]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1050;
const int M = 1e5 + 50;
const ll inf = 1e18;

int n, m, s, t;

struct flow_t {
	int n, m, s, t;
	int gap[N], head[N], cur[N], tot;
	ll preflow, precost, d[N], h[N];
	bool ins[N];
	struct edge_t {
		int to, nxt;
		ll w, c;
		edge_t() : to(0), nxt(0), w(0), c(0) {}
		edge_t(int to, int nxt, ll w, ll c) : to(to), nxt(nxt), w(w), c(c) {}
	} e[M];
	void init() {
		memset(head, 0, sizeof head);
		tot = 1;
		preflow = precost = 0;
	}
	flow_t() {
		init();
	}
	void add(int u, int v, ll w, ll c) {
		e[++tot] = edge_t(v, head[u], w, c); head[u] = tot;
		e[++tot] = edge_t(u, head[v], 0, -c); head[v] = tot;
	}
	void add(int u, int v, ll wl, ll wr, ll c) {
		if (c > 0) {
			gap[u] -= wl, gap[v] += wl;
			precost += wl * c;
			add(u, v, wr - wl, c);
		}
		else {
			gap[u] -= wr, gap[v] += wr;
			precost += wr * c;
			add(v, u, wr - wl, -c);
		}
	}
	void build() {
		for (int i = 1; i <= n; ++i) if (i != s && i != t) {
			if (gap[i] > 0) {
				add(s, i, gap[i], 0);
				preflow += gap[i];
			}
			else {
				add(i, t, -gap[i], 0);
			}
		}
	}
	bool spfa() {
		fill(d, d + n + 1, inf);
		fill(h, h + n + 1, 0);
		queue<int> que;
		que.emplace(s);
		d[s] = 0; ins[s] = true;
		while (!que.empty()) {
			int x = que.front(); que.pop();
			ins[x] = false;
			for (int i = head[x]; i; i = e[i].nxt) {
				int y = e[i].to;
				ll w = e[i].w, c = e[i].c;
				if (w && d[y] > d[x] + c) {
					d[y] = d[x] + c;
					if (!ins[y]) {
						ins[y] = true;
						que.emplace(y);
					}
				}
			}
		}
		return d[t] < inf;
	}
	bool dijkstra() {
		fill(d, d + n + 1, inf);
		memcpy(cur, head, sizeof head);
		priority_queue<pair<ll, int>> que;
		d[s] = 0;
		que.emplace(-d[s], s);
		while (!que.empty()) {
			auto [_d, x] = que.top(); que.pop();
			if (-d[x] != _d) continue;
			for (int i = head[x]; i; i = e[i].nxt) {
				int y = e[i].to; ll w = e[i].w, c = e[i].c + h[x] - h[y];
				if (w && d[y] > d[x] + c) {
					d[y] = d[x] + c;
					que.emplace(-d[y], y);
				}
			}
		}
		return d[t] < inf;
	}
	ll go(int x, ll flow) {
		if (x == t) return flow;
		ll rest = flow;
		ins[x] = true;
		for (int &i = cur[x]; i; i = e[i].nxt) {
			int y = e[i].to; ll w = e[i].w, c = e[i].c + h[x] - h[y];
			if (w && d[y] == d[x] + c && !ins[y]) {
				ll k = go(y, min(w, rest));
				e[i].w -= k;
				e[i ^ 1].w += k;
				rest -= k;
				if (!rest) break;
			}
		}
		ins[x] = false;
		return flow - rest;
	}
	void update() {
		for (int i = 1; i <= n; ++i)
			if (d[i] < inf)
				h[i] += d[i];
	}
	pair<ll, ll> solve() {
		if (!spfa()) return make_pair(0, 0);
		update();
		ll mincost = 0;
		ll maxflow = 0;
		while (dijkstra()) {
			ll f = go(s, inf);
			assert(f > 0);
			update();
			maxflow += f;
			mincost += h[t] * f;
		}
		return make_pair(maxflow, mincost);
	}
} G;

int main() {
	cin >> n >> m >> s >> t;
	G.n = n + 2;
	G.s = n + 1;
	G.t = G.s + 1;
	for (int i = 1; i <= m; ++i) {
		int x, y, wl, wr, c;
		cin >> x >> y >> wl >> wr >> c;
		G.add(x, y, wl, wr, c);
	}
	G.build();
	G.add(t, s, inf, 0);
	auto p = G.solve();
	if (p.first != G.preflow) {
		cout << -1 << '\n';
		return 0;
	}
	G.n -= 2;
	ll base = G.e[G.tot].w;
	for (int i = G.tot - 1; i <= G.tot; ++i)
		G.e[i].w = 0;
	G.s = s, G.t = t;
	auto q = G.solve();
	cout << q.first + base << ' ' << p.second + q.second + G.precost<< '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 5992kb

input:

3 3 1 3
1 2 0 6 0
2 3 1 1000 4
2 3 0 1000 3

output:

6 19

result:

ok 2 number(s): "6 19"

Test #2:

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

input:

5 6 2 4
2 1 1 6 4
2 3 0 5 1
1 3 2 8 2
3 4 1 7 1
3 5 0 4 1
5 4 1 5 2

output:

11 60

result:

ok 2 number(s): "11 60"

Test #3:

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

input:

3 1 1 3
2 3 1 100 -100

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

6 20 3 2
2 6 31 62 -14
6 5 18 75 -5
3 4 19 46 -94
3 6 6 47 -84
4 5 1 100 38
3 4 1 33 -64
1 2 31 59 92
6 2 1 74 -17
3 4 40 40 0
6 3 18 95 67
3 1 22 99 -87
5 4 19 33 -59
3 5 24 74 13
5 2 19 83 22
2 1 3 10 -81
3 1 6 76 -21
3 5 12 46 60
5 3 17 55 92
2 4 1 7 42
4 2 79 99 -3

output:

248 -6071

result:

ok 2 number(s): "248 -6071"

Test #5:

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

input:

6 20 5 4
5 2 1624 533269 -139880
2 4 0 15565 24058
1 3 0 0 0
2 5 2565 220226 604019
3 4 1165 51064 264995
2 6 0 84605 801197
1 5 0 375912 438852
4 6 2025 677043 359279
4 3 2078 15429 -606365
5 4 3253 669243 288789
3 4 2991 988592 -599399
5 6 1159 792735 -727904
5 2 941 159641 90003
5 4 4264 987824 5...

output:

3268997 -609038394670

result:

ok 2 number(s): "3268997 -609038394670"

Test #6:

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

input:

6 20 3 4
4 2 70379 363446 -216271
3 1 40731 817362 -610850
5 3 45928 603804 335372
4 1 14839 889225 279553
1 4 111451 645417 -660802
3 1 30534 887172 -788179
5 4 9595 15783 559723
5 4 19320 892283 -997184
6 1 13966 926157 -279930
2 6 55766 969481 923720
2 1 1626 793658 587430
3 4 16341 717826 -86874...

output:

2372477 -1008282590271

result:

ok 2 number(s): "2372477 -1008282590271"

Test #7:

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

input:

6 20 2 6
3 6 57096 162636 663483
6 3 12879 401950 150875
4 2 55557 991364 274301
5 3 61117 989768 675838
3 5 55211 396391 -748348
6 5 17586 268092 -668494
3 1 70661 347360 -227828
1 5 77878 599932 864205
4 2 13723 426224 -496803
4 1 0 909998 -272175
2 4 69280 512330 -751788
6 5 35697 973744 -72290
5...

output:

1434247 -19122258462

result:

ok 2 number(s): "1434247 -19122258462"

Test #8:

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

input:

50 500 15 26
5 39 0 212962 -400202
39 33 749 159440 617413
43 34 819 997092 825049
34 48 1534 318958 -144695
11 37 0 983399 -329393
19 33 0 843486 988506
32 45 1334 729326 -938178
37 9 963 626078 349608
34 42 0 243498 -20646
11 17 1011 945863 -627218
7 32 0 756672 920090
8 26 1776 807376 -455829
13 ...

output:

13894271 -34225425128509

result:

ok 2 number(s): "13894271 -34225425128509"

Test #9:

score: 0
Accepted
time: 18ms
memory: 5872kb

input:

50 1000 29 12
9 34 782 375064 127907
4 40 2085 764570 -90435
43 8 1460 166821 4596
11 35 826 470840 555882
16 46 0 812869 937386
1 12 405 670247 125943
36 38 0 85327 911102
29 33 558 81202 -394257
38 17 0 939407 175104
31 34 1360 547503 180904
37 27 0 536387 -87498
23 19 0 744774 -83406
12 34 0 6048...

output:

16141906 -91411803962527

result:

ok 2 number(s): "16141906 -91411803962527"

Test #10:

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

input:

50 500 41 39
25 32 10892 96360 200856
13 24 916 878509 701236
41 38 2498 56477 -277527
5 34 4978 182292 740911
18 10 6455 733105 989389
2 49 3105 72791 354971
23 34 3337 676388 365240
28 31 3871 101717 -460592
27 3 3076 536700 264447
41 43 3299 963677 -239011
24 33 3544 213942 -760051
18 39 2809 221...

output:

15723908 -35056194400006

result:

ok 2 number(s): "15723908 -35056194400006"

Test #11:

score: 0
Accepted
time: 18ms
memory: 5984kb

input:

50 1000 23 30
37 35 903 256723 827278
46 32 1509 53354 -600251
23 27 782 528624 907754
14 10 433 725919 957890
39 7 221 59498 -722846
2 7 1364 868063 815478
15 17 2289 571446 -257636
26 6 2705 960604 -465141
19 31 1089 902070 -969714
21 17 2552 651978 867173
24 2 1066 609780 -820634
20 15 1713 99315...

output:

20935812 -101080647346631

result:

ok 2 number(s): "20935812 -101080647346631"

Test #12:

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

input:

50 500 11 3
39 5 24154 413052 205168
2 33 9529 541066 424543
34 3 16649 794388 197716
34 23 21794 588796 883090
24 39 28843 143048 -199922
4 45 14611 978980 -517850
18 33 49112 584887 -895326
9 8 26436 637602 968040
46 31 31657 220325 -42763
45 7 15871 559299 702791
5 4 49864 83225 -624236
14 13 218...

output:

13665538 -38120035984842

result:

ok 2 number(s): "13665538 -38120035984842"

Test #13:

score: 0
Accepted
time: 17ms
memory: 5924kb

input:

50 1000 48 28
49 3 8973 992305 456075
19 28 6274 999944 944105
42 31 18444 84155 927380
20 35 23136 260274 878320
34 20 13729 548312 -909235
44 4 13089 286792 429914
49 33 7793 348091 66713
8 16 12852 142118 888601
47 24 15223 53363 -416012
1 48 15878 138026 255612
36 37 13937 731566 966874
22 34 16...

output:

16133026 -98703594100601

result:

ok 2 number(s): "16133026 -98703594100601"

Test #14:

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

input:

50 500 15 8
49 48 40983 609788 -37099
11 35 57810 653761 892772
34 47 15798 999787 464642
22 13 85779 860378 839353
17 21 32282 898304 -627263
49 20 34703 469070 -672512
25 33 73215 632814 233722
6 8 101071 363704 587018
21 36 107035 589881 -418601
14 16 82595 573207 -585063
41 20 87473 755950 98771...

output:

17121568 -37734255010971

result:

ok 2 number(s): "17121568 -37734255010971"

Test #15:

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

input:

50 1000 2 41
9 28 46576 220919 426564
21 25 35782 999199 -255105
13 31 22103 60319 -970608
20 42 69794 788521 -653078
19 7 58425 318051 -358974
19 11 49686 527789 791115
5 10 44593 167664 -784621
30 15 24518 467971 797692
6 20 50096 735904 -229790
49 20 36221 64498 -400378
29 10 20624 32279 -844830
...

output:

23605188 -101167595426821

result:

ok 2 number(s): "23605188 -101167595426821"

Test #16:

score: 0
Accepted
time: 830ms
memory: 5988kb

input:

500 5000 281 370
104 141 24928 399165 318883
465 458 13354 998793 -484579
360 479 15492 714564 500923
14 10 21965 962142 986486
330 429 6839 119285 984012
56 305 6479 100934 -826957
97 151 7627 619199 546926
102 224 17467 506542 -555847
482 16 3106 131352 45305
316 252 36357 906300 868577
11 352 183...

output:

34847519 -444887888307815

result:

ok 2 number(s): "34847519 -444887888307815"

Test #17:

score: 0
Accepted
time: 71ms
memory: 6120kb

input:

1000 1000 329 501
642 456 0 303370 745624
404 687 0 952485 -488473
148 172 0 61082 -973829
217 61 0 676342 -927881
927 935 0 876728 -412472
918 781 0 425479 -136952
118 652 0 559605 -719695
823 902 0 361443 694308
676 331 0 248417 -759727
922 359 0 806571 667500
319 702 0 513441 -768840
85 742 0 962...

output:

0 25391368368

result:

ok 2 number(s): "0 25391368368"

Test #18:

score: 0
Accepted
time: 74ms
memory: 6064kb

input:

1000 1000 68 678
177 442 0 174955 -605128
901 797 0 889103 -803112
430 49 0 560456 999218
660 263 0 589544 -984111
666 227 0 595986 6222
163 678 0 487372 -762185
932 463 0 142928 -756402
513 374 0 86019 158660
980 222 0 97407 -817946
769 412 0 278390 -98326
632 272 0 4286 -535349
157 437 0 19750 375...

output:

49350 -50607990524

result:

ok 2 number(s): "49350 -50607990524"

Test #19:

score: 0
Accepted
time: 334ms
memory: 5952kb

input:

1000 2000 289 539
336 369 6499 107222 319238
616 105 12063 655949 991994
953 228 15875 324902 657386
913 523 0 716138 -197
676 726 0 579348 889086
707 996 0 554031 -913100
307 201 0 52022 -314985
452 666 15028 81970 -418183
175 539 35105 363649 -5018
214 785 0 558699 -337890
511 323 4752 355738 9226...

output:

5999179 -26019371993017

result:

ok 2 number(s): "5999179 -26019371993017"

Test #20:

score: 0
Accepted
time: 685ms
memory: 6156kb

input:

1000 3000 806 399
975 881 7262 72158 687818
50 838 2575 489162 592083
146 752 0 729780 886803
448 853 0 467811 308183
942 600 39644 766436 -275212
71 241 33009 604439 505199
279 595 3605 567878 62565
559 648 32675 819733 -114862
346 159 4559 9698 108900
69 849 5798 583360 -84177
198 540 14175 19515 ...

output:

8698539 -106302791961013

result:

ok 2 number(s): "8698539 -106302791961013"

Test #21:

score: 0
Accepted
time: 1424ms
memory: 6140kb

input:

1000 5000 248 17
798 971 5562 166715 877758
514 944 14428 836703 -615339
311 692 5260 40829 916168
181 714 1594 823163 18587
847 870 19271 827541 -517441
946 310 4699 460521 -737871
435 570 5367 274153 -186395
312 720 11335 974940 -968280
946 425 4263 808924 -690207
661 872 9274 116440 611161
855 11...

output:

13538466 -348967770000544

result:

ok 2 number(s): "13538466 -348967770000544"

Test #22:

score: 0
Accepted
time: 1558ms
memory: 6036kb

input:

1000 5000 335 892
81 448 34513 444814 716767
740 544 44777 949704 274318
190 722 23066 101746 622944
946 454 363 35002 360283
222 626 4464 693792 -709886
220 173 22835 304823 -612622
441 816 13311 468419 -456262
390 376 16924 721511 834972
14 107 11597 91042 130955
872 311 1882 790437 237497
264 473...

output:

29282723 -326686986015291

result:

ok 2 number(s): "29282723 -326686986015291"

Test #23:

score: 0
Accepted
time: 1574ms
memory: 6112kb

input:

1000 5000 331 338
431 204 14386 771648 740204
281 19 43 74222 362047
702 690 3290 779701 201867
779 34 6703 670699 74531
533 757 12642 36559 -936215
76 953 36889 343239 -623625
909 168 10496 768983 -114706
519 958 15097 73213 -993240
387 374 4856 85052 -840616
879 338 22002 763083 18933
964 543 7060...

output:

28016777 -329477934757237

result:

ok 2 number(s): "28016777 -329477934757237"

Test #24:

score: 0
Accepted
time: 1663ms
memory: 6036kb

input:

1000 5000 85 216
718 237 5977 392706 -485547
808 72 0 360740 990712
815 509 13783 933495 913113
224 479 5804 858119 -22296
475 531 1490 348416 -852046
876 807 5415 275592 -204849
114 991 16506 513922 90180
972 956 13392 842463 982593
861 206 7442 995725 603009
813 210 12012 735286 497228
675 216 0 6...

output:

33304587 -310312433309877

result:

ok 2 number(s): "33304587 -310312433309877"

Test #25:

score: 0
Accepted
time: 1697ms
memory: 6168kb

input:

1000 5000 233 373
900 671 0 424558 399591
801 565 7542 265469 780149
289 688 10566 545513 -186326
803 627 1038 981105 -750051
591 797 11 917205 645607
971 934 18345 456747 180843
931 648 24749 665297 637396
82 335 10523 594448 -229124
166 674 10013 260824 -834049
194 498 12823 213968 923260
323 367 ...

output:

33263232 -321943865677110

result:

ok 2 number(s): "33263232 -321943865677110"

Test #26:

score: 0
Accepted
time: 1638ms
memory: 6076kb

input:

1000 5000 364 679
241 79 4898 560222 -902209
940 907 8447 354220 -360989
619 412 40326 571760 366130
910 745 2292 25769 326643
91 12 4971 127973 742938
322 204 31182 426801 305633
506 244 13832 769833 -974527
300 324 14592 834409 -270222
15 425 0 768111 663648
10 207 24491 920830 466912
17 693 17579...

output:

48646091 -275455005459403

result:

ok 2 number(s): "48646091 -275455005459403"

Test #27:

score: 0
Accepted
time: 1966ms
memory: 6168kb

input:

1000 5000 933 228
206 228 15327 275686 985028
882 573 313 948888 -815623
544 9 1436 769936 233130
885 228 8146 653541 997950
749 902 22111 344680 798769
453 666 60080 426599 896661
78 438 58289 81973 989235
315 228 23039 177059 -496477
580 577 44756 245320 -28988
416 842 10042 981717 839733
552 492 ...

output:

107177048 -292368356606276

result:

ok 2 number(s): "107177048 -292368356606276"

Test #28:

score: 0
Accepted
time: 2045ms
memory: 5988kb

input:

1000 5000 206 584
155 809 0 300382 -474253
155 994 79 70848 120744
476 246 23401 92938 -915430
452 808 22095 278707 558893
539 982 57354 885170 -761257
170 584 12058 814511 -145493
104 723 14014 770567 -899978
783 584 11320 744106 -496552
173 979 17009 513277 429382
359 568 29028 877760 970368
914 1...

output:

148850020 -223299573015245

result:

ok 2 number(s): "148850020 -223299573015245"

Test #29:

score: 0
Accepted
time: 1900ms
memory: 6060kb

input:

1000 5000 140 675
196 282 9182 828209 -503719
93 445 0 140283 -135183
596 123 8599 815365 816974
135 264 5622 25495 -766990
351 721 7466 106977 -155302
865 675 11515 204511 -97156
388 693 23236 799923 -557331
129 809 13316 466181 -836445
722 546 14116 449229 773535
140 659 19546 192249 -336816
433 5...

output:

145492839 -247490323782779

result:

ok 2 number(s): "145492839 -247490323782779"

Test #30:

score: 0
Accepted
time: 1833ms
memory: 5992kb

input:

1000 5000 931 272
50 873 7609 47533 -541139
4 272 14101 473798 -234092
931 690 13993 721488 186151
162 269 16957 389284 -393731
729 733 34902 83042 -724763
134 272 11923 999883 -726588
364 391 1650 85571 597008
556 16 1421 791030 -65237
549 272 4611 826224 -239936
748 967 2393 330209 -635818
464 909...

output:

144621615 -255096018217124

result:

ok 2 number(s): "144621615 -255096018217124"

Test #31:

score: 0
Accepted
time: 2035ms
memory: 6068kb

input:

1000 5000 739 467
309 832 2966 593332 973245
330 792 0 986911 -757580
625 467 7052 987457 -240020
537 436 0 762179 -286018
753 181 16702 980108 -27682
488 139 0 787274 -797812
733 725 28352 471108 -507002
780 58 2719 508351 -62601
122 465 1878 490135 -499442
366 969 7733 785035 -864344
504 859 0 346...

output:

151722353 -238428050831473

result:

ok 2 number(s): "151722353 -238428050831473"

Test #32:

score: 0
Accepted
time: 1800ms
memory: 5932kb

input:

1000 5000 547 788
336 623 11955 15897 -330749
401 57 34699 307352 468156
547 567 10789 889434 -831117
547 900 15607 487643 -498536
739 702 24600 154886 218882
327 942 27457 999628 841224
225 788 14223 893439 283724
106 996 5028 359069 901494
201 723 7324 571597 792922
623 775 18907 978410 314595
818...

output:

143626839 -212170251457291

result:

ok 2 number(s): "143626839 -212170251457291"

Test #33:

score: 0
Accepted
time: 1987ms
memory: 5932kb

input:

1000 5000 109 613
569 53 7224 159873 -175897
472 785 2950 75217 -296263
786 919 42901 274729 550899
399 494 2541 391513 -86935
118 838 3815 429821 308082
713 896 8472 960557 -378401
264 892 3174 535220 -673876
7 623 15968 942856 67725
956 298 13021 502212 -678713
421 89 6504 256909 807311
250 196 14...

output:

144036529 -240215991129164

result:

ok 2 number(s): "144036529 -240215991129164"

Test #34:

score: 0
Accepted
time: 2026ms
memory: 6184kb

input:

1000 5000 391 698
242 698 23398 524160 -2875
115 634 10453 571042 622631
675 156 9639 797698 822771
618 43 657 371060 -180346
134 627 26210 841601 280491
141 35 8219 484375 512
349 698 6895 126675 544310
259 350 2711 379576 799953
886 773 11125 367356 -289414
652 783 16216 795765 -266269
511 112 217...

output:

150199210 -230912175333369

result:

ok 2 number(s): "150199210 -230912175333369"

Test #35:

score: 0
Accepted
time: 1951ms
memory: 6068kb

input:

1000 5000 536 489
438 423 28858 606033 -161657
573 546 7472 934736 599822
567 188 9740 463001 457328
41 729 6807 933755 790788
29 724 0 754170 952168
163 489 3491 505399 725339
80 648 3870 74788 311827
536 622 9034 141507 554191
841 40 2119 6802 -95457
847 492 12769 390865 -380032
536 22 11076 20817...

output:

228212746 -191757425672435

result:

ok 2 number(s): "228212746 -191757425672435"

Test #36:

score: 0
Accepted
time: 2005ms
memory: 6048kb

input:

1000 5000 741 397
493 397 13451 346424 -561315
198 756 8598 735377 -754855
667 882 6228 9867 -335027
339 476 0 428636 -28242
597 68 3593 733789 735118
257 215 6545 761499 -955668
222 822 11030 599815 -379034
371 397 2706 808032 -7987
76 883 7692 826349 313053
271 397 4621 220057 487106
825 76 7478 1...

output:

144499952 -242630820111524

result:

ok 2 number(s): "144499952 -242630820111524"

Test #37:

score: 0
Accepted
time: 1086ms
memory: 6080kb

input:

1000 5000 152 556
9 341 3771 355355 -855078
570 823 2987 341744 149967
169 491 49218 181978 -448601
390 528 13118 782248 213613
336 805 7858 132880 -801241
848 301 23568 482253 400317
189 904 3771 463726 376912
406 796 41424 270963 -152461
633 669 11289 135169 299609
480 386 8405 243959 328569
815 4...

output:

-1

result:

ok 1 number(s): "-1"

Test #38:

score: 0
Accepted
time: 1082ms
memory: 5996kb

input:

1000 5000 289 525
11 295 17308 401605 -681085
466 687 22781 692572 -783748
956 17 12765 310639 221912
375 671 11746 748129 -272468
309 829 20303 869617 -860006
150 374 6565 71633 283208
166 650 60069 833189 -662572
246 93 2968 118416 -92332
915 525 15887 112847 829500
220 648 8676 98139 -19631
763 1...

output:

-1

result:

ok 1 number(s): "-1"

Test #39:

score: 0
Accepted
time: 2027ms
memory: 5996kb

input:

1000 5000 254 92
944 522 16698 849881 -149801
875 92 12069 49550 -606547
492 823 5541 373513 -386719
980 788 17283 986977 676479
271 493 1870 683452 751918
159 882 27525 305257 779710
988 868 6990 634950 343507
483 217 8603 999987 -87701
767 568 5295 379759 598420
671 189 6115 701694 -512886
972 904...

output:

239603483 -158694085808920

result:

ok 2 number(s): "239603483 -158694085808920"

Test #40:

score: 0
Accepted
time: 2010ms
memory: 5984kb

input:

1000 5000 534 246
711 701 0 630175 124080
123 807 16501 838328 369705
200 796 22459 755283 854608
654 258 9342 482939 160862
962 340 15165 672606 922533
155 731 22085 933465 903178
338 597 12071 247849 -482139
388 933 1757 716322 -866429
19 543 998 317542 -696521
457 246 13566 45552 -860363
534 958 ...

output:

137826221 -246223007039699

result:

ok 2 number(s): "137826221 -246223007039699"

Test #41:

score: 0
Accepted
time: 1832ms
memory: 6164kb

input:

1000 5000 323 190
351 34 6039 703904 -241657
33 978 19118 677300 793269
417 5 17497 748233 -425177
202 802 18705 976056 714523
794 694 5076 368922 592561
472 688 17913 641137 589194
425 784 18528 355757 802646
710 467 18116 416644 792572
87 116 6237 564281 752619
857 872 3799 9213 915257
419 946 203...

output:

125711894 -263417304091920

result:

ok 2 number(s): "125711894 -263417304091920"

Test #42:

score: 0
Accepted
time: 1750ms
memory: 6000kb

input:

1000 5000 247 561
129 767 15082 994677 -487040
524 986 8752 916746 -4624
226 142 8986 692155 791292
801 639 4385 514261 272261
417 79 4553 981494 458671
541 803 4670 296052 -933521
310 494 1382 833336 -917169
509 948 3404 848217 781732
315 290 22031 625173 -682118
641 101 1664 722700 -1819
809 508 9...

output:

129446151 -279645239058344

result:

ok 2 number(s): "129446151 -279645239058344"

Test #43:

score: 0
Accepted
time: 1875ms
memory: 6116kb

input:

1000 5000 515 362
577 362 6333 740731 965199
187 990 10360 809082 584738
265 667 12394 304855 -840288
528 172 6908 460731 -180949
925 587 16819 397384 -796567
131 783 12526 377282 -6515
875 246 4549 500117 186232
238 759 16131 361172 -555685
564 994 11149 45212 590362
730 810 11212 353913 247112
26 ...

output:

144823713 -248197179239599

result:

ok 2 number(s): "144823713 -248197179239599"

Test #44:

score: 0
Accepted
time: 1953ms
memory: 5948kb

input:

1000 5000 377 971
218 432 6164 14417 625673
53 246 6954 475442 960998
843 791 20186 187234 324378
319 506 6097 20757 -521230
896 808 20639 529583 -10866
521 289 9267 167241 745577
404 722 8010 867178 -226178
832 373 14508 718821 -136773
919 44 7499 750069 -98328
52 189 11899 913637 -587851
470 16 14...

output:

100552728 -269145914555129

result:

ok 2 number(s): "100552728 -269145914555129"

Test #45:

score: 0
Accepted
time: 1785ms
memory: 6060kb

input:

1000 5000 395 496
242 68 44639 849642 634662
322 852 37495 699776 473640
406 404 11526 506183 547552
692 993 30357 899002 -938946
983 274 10503 89183 -724703
766 161 116665 621828 -434027
251 21 21713 56887 -285514
179 136 0 842737 691203
943 307 24361 206123 -402023
895 148 17189 113651 904898
144 ...

output:

74126055 -304903466992658

result:

ok 2 number(s): "74126055 -304903466992658"

Test #46:

score: 0
Accepted
time: 1885ms
memory: 6156kb

input:

1000 5000 879 977
422 3 23737 496496 794736
845 843 8019 611198 56216
549 101 3899 868299 -724064
193 920 24925 909932 -680765
125 311 21367 31620 242826
607 592 8400 132680 458133
232 283 5630 554059 -587186
487 165 31022 595329 841358
367 745 11640 756686 -781994
986 543 13341 31253 334440
332 227...

output:

74199730 -306957895488542

result:

ok 2 number(s): "74199730 -306957895488542"

Test #47:

score: 0
Accepted
time: 1160ms
memory: 6004kb

input:

1000 5000 801 651
361 185 5553 862932 752974
680 328 18329 546156 111886
359 241 15577 236613 -863333
409 776 1473 347863 189783
509 174 3949 767905 -888057
60 37 17055 80697 -969959
604 163 14273 803517 -397078
664 572 4284 758103 760919
432 991 15056 360536 992644
83 4 11582 909733 108486
109 922 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #48:

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

input:

1000 5000 366 572
480 708 14920 366695 968540
712 119 54509 399398 389553
181 572 2843 870921 267895
353 229 8635 393860 -5245
856 511 6125 609060 -256787
611 729 4124 924518 270694
485 184 1541 676296 726111
958 686 6215 938551 914636
596 472 6545 910185 187068
510 153 9478 336865 -862897
626 938 3...

output:

76123109 -303819017690863

result:

ok 2 number(s): "76123109 -303819017690863"

Test #49:

score: 0
Accepted
time: 2059ms
memory: 6004kb

input:

1000 5000 80 300
611 260 21096 497076 42907
495 418 39685 267827 693705
944 122 9442 658753 54999
936 362 13040 108189 869000
511 300 2701 423986 -766165
195 997 12684 108839 374264
81 283 47107 504860 -144173
33 304 99839 868704 -465663
906 147 12865 92924 -784253
440 284 4378 577584 856259
835 713...

output:

80413796 -258653719624958

result:

ok 2 number(s): "80413796 -258653719624958"

Test #50:

score: 0
Accepted
time: 1739ms
memory: 5984kb

input:

1000 5000 491 189
5 571 7775 898777 410199
456 189 18546 399814 -492807
318 118 18018 551961 -572242
296 19 10626 21661 781489
491 322 25681 739193 -352920
619 351 16350 257366 -765023
145 159 10664 113363 -25733
108 728 10957 970706 893617
94 866 34544 591659 252634
977 152 23327 783294 -680794
807...

output:

76300839 -295224850280014

result:

ok 2 number(s): "76300839 -295224850280014"

Test #51:

score: 0
Accepted
time: 1812ms
memory: 6112kb

input:

1000 5000 624 211
677 963 8381 683092 495356
203 404 4075 177895 341880
289 656 28350 872936 -868758
838 728 2957 413978 -199379
288 926 16783 379769 -411974
957 712 11395 224204 537658
436 211 85368 649190 134245
186 797 8029 742355 -577541
354 277 6819 22296 -373919
833 451 18936 137827 282544
246...

output:

317994083 -116441746476196

result:

ok 2 number(s): "317994083 -116441746476196"

Test #52:

score: 0
Accepted
time: 1846ms
memory: 6076kb

input:

1000 5000 900 967
242 967 17078 513941 582905
895 278 13118 370483 871998
636 282 2871 92430 875551
364 882 7048 253843 -15333
81 129 24863 367479 -414480
952 35 57437 427346 426196
900 768 13153 226737 570567
840 967 20460 26394 -335929
900 718 8481 577594 669288
917 417 24358 267262 569835
197 644...

output:

341738518 -79763660364456

result:

ok 2 number(s): "341738518 -79763660364456"

Test #53:

score: 0
Accepted
time: 1829ms
memory: 6044kb

input:

1000 5000 15 153
217 482 14799 868861 199814
718 74 6279 565002 218354
852 179 12994 418209 -797309
863 153 9860 969548 -265651
236 981 5067 278742 874027
566 348 0 858227 -55352
728 537 30793 270111 728984
448 252 19803 288897 -913514
220 74 1849 82181 528776
809 786 11646 390174 -476272
561 591 85...

output:

322000936 -136244459593170

result:

ok 2 number(s): "322000936 -136244459593170"

Test #54:

score: 0
Accepted
time: 1547ms
memory: 5980kb

input:

1000 5000 376 700
272 111 3473 649716 374234
579 74 4351 484039 -695712
38 108 18880 900175 904069
64 280 13591 874364 877132
749 700 2621 853505 754126
100 700 5913 897769 -766687
878 700 7702 223746 -494795
854 700 7902 152561 912948
377 887 41035 294218 -137141
376 487 4344 761067 -797453
711 45 ...

output:

401097621 -95489447383864

result:

ok 2 number(s): "401097621 -95489447383864"

Test #55:

score: 0
Accepted
time: 1534ms
memory: 6000kb

input:

1000 5000 331 384
837 384 9217 851000 660225
326 606 44166 606427 528527
663 384 7771 112057 492577
981 870 4246 336180 -239733
679 26 2193 974910 -515992
572 384 20024 291812 -879414
803 174 4942 737073 -652149
692 631 818 886838 774780
300 218 29851 778316 67581
331 697 4923 698601 -661928
653 563...

output:

400326981 -88424295809831

result:

ok 2 number(s): "400326981 -88424295809831"

Test #56:

score: 0
Accepted
time: 1634ms
memory: 5984kb

input:

1000 5000 446 569
669 209 17884 899363 -785074
182 288 2862 635694 -80875
299 508 28337 924297 643185
168 950 2389 365517 -364776
737 569 3486 869075 404647
217 52 5267 176272 78074
93 870 43906 464626 211361
446 310 8208 484302 -941722
446 28 4979 800714 -14708
446 873 7451 372003 216509
37 875 173...

output:

401478586 -98602206576104

result:

ok 2 number(s): "401478586 -98602206576104"