457_B. Distributed Join_28640
Piegirl was asked to implement two table join operation for distributed database system, minimizing the network traffic.

Suppose she wants to join two tables, A and B. Each of them has certain number of rows which are distributed on different number of partitions. Table A is distributed on the first cluster consisting of m partitions. Partition with index i has ai rows from A. Similarly, second cluster containing table B has n partitions, i-th one having bi rows from B. 

In one network operation she can copy one row from any partition to any other partition. At the end, for each row from A and each row from B there should be a partition that has both rows. Determine the minimal number of network operations to achieve this.

Input

First line contains two integer numbers, m and n (1 ≤ m, n ≤ 105). Second line contains description of the first cluster with m space separated integers, ai (1 ≤ ai ≤ 109). Similarly, third line describes second cluster with n space separated integers, bi (1 ≤ bi ≤ 109).

Output

Print one integer — minimal number of copy operations.

Examples

Input

2 2
2 6
3 100


Output

11


Input

2 3
10 10
1 1 1


Output

6

Note

In the first example it makes sense to move all the rows to the second partition of the second cluster which is achieved in 2 + 6 + 3 = 11 operations

In the second example Piegirl can copy each row from B to the both partitions of the first cluster which needs 2·3 = 6 copy operations.
m, n = map(int, raw_input().split())
a = map(int, raw_input().split())
b = map(int, raw_input().split())
a.sort()
b.sort()
a.reverse()
b.reverse()
sa, sb = [a[0]], [b[0]]
for i in range(1, m):
	sa.append(sa[i-1] + a[i])
for i in range(1, n):
	sb.append(sb[i-1] + b[i])
aa, bb = sa[m-1], sb[n-1]
ans = 9999999999999999999999999999;
for i in range(m):
	ans = min(ans, aa - sa[i] + bb *(i + 1) );
for i in range(n):
	ans = min(ans, bb - sb[i] + aa * (i + 1));
print ans



2 2
2 6
3 100
 2 3
10 10
1 1 1
 10 10
269584761 865524829 265226347 963092340 261501474 16861445 221090297 746538035 842020225 649641719
49728483 423679832 107851851 179960003 345895125 400584885 460489835 377856735 506736683 676996548
 3 4
337369924 278848730 654933675
866361693 732544605 890800310 350303294
 8 8
808147225 623333304 535665685 469385259 122918604 200681823 800211367 286974812
85215517 983921829 274028967 567054904 144473212 964018990 177471567 73882806
 10 10
458278487 288667180 648471199 581765640 758405216 589361337 319325955 938498114 249892107 138299026
57775135 470751607 454623764 556600014 141039336 225043834 692497485 517610562 635337211 56258907
 10 10
933168403 835157665 823216696 818565876 448948583 884328249 809244579 473034231 407137956 871269623
653126539 145998557 644003076 138712151 839886312 479712343 709513279 138285801 858528549 643830064
 6 5
4689556 6609945 15705705 10301912 11245669 5844638
440894622 898226832 22060902 222576920 53133033
 5 6
574664105 497253985 200935113 926362846 223381305
34188719 14075259 27219005 9682257 14352213 11696423
 20 30
81 67 100 83 97 97 58 54 72 78 59 64 55 85 75 58 79 91 64 84
116 13 114 180 17 123 64 185 170 54 138 142 89 191 78 152 49 5 121 66 163 171 64 170 143 143 126 12 175 84
 1 1
1889
2867
 5 4
556840201 669601415 674042771 93322040 157280418
253115131 933556803 294280580 169051325
 6 5
45936257 8169878 14134346 26323055 65863745 50728147
997339869 2970526 163305525 839524148 193404120
 5 6
7780674 1861750 4491902 10256124 14362475
1809567 5616386 1771573 2099536 1113026 3938402
 5 7
473347111 640932948 320036306 595696211 365475226
347859328 553364017 687935743 145411543 689180757 696504973 783694820
 5 6
284534195 993347068 628813225 512761241 835859363
61567950 7311163 14322159 100466429 66443161 48573213
 10 10
510955240 684852706 455356451 284505713 595775142 646334608 563116339 941123613 818750895 516673753
382626402 204542396 341363992 234231105 75079663 683639780 624391764 265169060 686304227 280991725
 2 2
888381664 866366630
170399907 404233949
 10 10
326151338 981287141 830123412 482457331 77554645 351237238 663827505 549778905 967488359 954617100
238752550 787656851 393452025 837732771 522417885 876998499 195063055 325140429 546151936 403260186
 6 5
40192277 37957130 22509015 95257198 6210193 16850057
76289330 265203569 184343840 163207736 126924648
 10 10
269584761 865524829 265226347 963092340 261501474 16861445 221090297 746538035 842020225 649641719
49728483 423679832 107851851 179960003 345895125 400584885 460489835 377856735 403077618 676996548
 3 4
337369924 278848730 18889610
866361693 732544605 890800310 350303294
 8 8
808147225 623333304 535665685 469385259 122918604 200681823 800211367 286974812
14713330 983921829 274028967 567054904 144473212 964018990 177471567 73882806
 10 10
458278487 288667180 648471199 581765640 758405216 589361337 319325955 938498114 249892107 138299026
57775135 470751607 454623764 556600014 141039336 225043834 692497485 517610562 635337211 67151601
 10 10
933168403 308417110 823216696 818565876 448948583 884328249 809244579 473034231 407137956 871269623
653126539 145998557 644003076 138712151 839886312 479712343 709513279 138285801 858528549 643830064
 20 30
81 67 100 83 97 97 58 54 72 78 59 64 55 85 75 58 79 91 64 84
116 13 114 108 17 123 64 185 170 54 138 142 89 191 78 152 49 5 121 66 163 171 64 170 143 143 126 12 175 84
 5 4
556840201 669601415 674042771 90966172 157280418
253115131 933556803 294280580 169051325
 6 5
45936257 8169878 14134346 26323055 65863745 50728147
997339869 4160924 163305525 839524148 193404120
 5 7
473347111 640932948 320036306 595696211 151648404
347859328 553364017 687935743 145411543 689180757 696504973 783694820
 5 6
284534195 993347068 628813225 512761241 835859363
61567950 7311163 14322159 70462813 66443161 48573213
 10 10
510955240 684852706 455356451 284505713 595775142 646334608 563116339 941123613 818750895 516673753
382626402 204542396 341363992 234231105 75079663 683639780 624391764 265169060 686304227 76939693
 2 2
888381664 866366630
170399907 723034416
 10 10
189739384 981287141 830123412 482457331 77554645 351237238 663827505 549778905 967488359 954617100
238752550 787656851 393452025 837732771 522417885 876998499 195063055 325140429 546151936 403260186
 6 5
40192277 37957130 22509015 95257198 6210193 16850057
76289330 265203569 184343840 282294387 126924648
 2 3
10 10
1 1 2
 10 10
269584761 865524829 265226347 963092340 261501474 16861445 221090297 746538035 842020225 649641719
49728483 423679832 107851851 301306305 345895125 400584885 460489835 377856735 403077618 676996548
 10 10
458278487 288667180 648471199 581765640 758405216 589361337 319325955 938498114 271204268 138299026
57775135 470751607 454623764 556600014 141039336 225043834 692497485 517610562 635337211 67151601
 10 10
933168403 308417110 823216696 818565876 448948583 884328249 809244579 473034231 407137956 871269623
1302355559 145998557 644003076 138712151 839886312 479712343 709513279 138285801 858528549 643830064
 20 30
81 67 100 83 97 97 58 54 72 78 59 64 55 85 75 58 79 91 64 84
116 13 114 108 17 123 64 185 170 54 138 142 89 191 78 152 49 5 121 66 163 171 64 170 143 143 126 12 175 165
 5 4
12962215 669601415 674042771 90966172 157280418
253115131 933556803 294280580 169051325
 5 7
905166376 640932948 320036306 595696211 151648404
347859328 553364017 687935743 145411543 689180757 696504973 783694820
 10 10
510955240 684852706 455356451 284505713 595775142 646334608 563116339 941123613 818750895 516673753
382626402 395268973 341363992 234231105 75079663 683639780 624391764 265169060 686304227 76939693
 10 10
189739384 981287141 830123412 482457331 77554645 351237238 663827505 549778905 967488359 954617100
238752550 787656851 393452025 837732771 522417885 876998499 380725999 325140429 546151936 403260186
 6 5
40192277 37957130 22509015 95257198 7950428 16850057
76289330 265203569 184343840 282294387 126924648
 2 3
10 10
0 1 2
 10 10
458278487 288667180 648471199 581765640 758405216 589361337 319325955 938498114 271204268 105888757
57775135 470751607 454623764 556600014 141039336 225043834 692497485 517610562 635337211 67151601
 10 10
933168403 308417110 823216696 818565876 448948583 884328249 809244579 473034231 407137956 871269623
1302355559 145998557 644003076 138712151 839886312 235562434 709513279 138285801 858528549 643830064
 20 30
81 67 100 83 97 97 58 54 72 78 59 64 55 85 75 58 79 91 64 84
116 13 114 108 17 123 64 185 170 54 138 142 89 191 78 152 49 5 121 66 163 171 81 170 143 143 126 12 175 165
 5 4
12962215 669601415 674042771 90966172 157280418
340301928 933556803 294280580 169051325
 6 5
45936257 10273743 14134346 26323055 65863745 50728147
1904649320 4160924 163305525 839524148 193404120
 5 7
905166376 640932948 97971905 595696211 151648404
347859328 553364017 687935743 145411543 689180757 696504973 783694820
 10 10
510955240 684852706 455356451 284505713 595775142 215459005 563116339 941123613 818750895 516673753
382626402 395268973 341363992 234231105 75079663 683639780 624391764 265169060 686304227 76939693
 10 10
81598156 981287141 830123412 482457331 77554645 351237238 663827505 549778905 967488359 954617100
238752550 787656851 393452025 837732771 522417885 876998499 380725999 325140429 546151936 403260186
 6 5
40192277 37957130 22509015 95257198 7950428 16850057
57089894 265203569 184343840 282294387 126924648
 2 3
10 10
0 1 0
 10 10
458278487 288667180 648471199 581765640 758405216 589361337 319325955 938498114 271204268 105888757
57775135 470751607 454623764 556600014 141039336 225043834 853643640 517610562 635337211 67151601
 10 10
933168403 308417110 823216696 818565876 448948583 884328249 775152756 473034231 407137956 871269623
1302355559 145998557 644003076 138712151 839886312 235562434 709513279 138285801 858528549 643830064
 20 30
81 67 100 83 128 97 58 54 72 78 59 64 55 85 75 58 79 91 64 84
116 13 114 108 17 123 64 185 170 54 138 142 89 191 78 152 49 5 121 66 163 171 81 170 143 143 126 12 175 165
 5 4
12962215 669601415 674042771 90966172 202082930
340301928 933556803 294280580 169051325
 6 5
45936257 10273743 14134346 26323055 65863745 50728147
1904649320 4160924 163305525 839524148 247355749
 5 7
905166376 640932948 97971905 595696211 151648404
347859328 553364017 687935743 145411543 689180757 489370467 783694820
 10 10
510955240 684852706 455356451 284505713 595775142 86948838 563116339 941123613 818750895 516673753
382626402 395268973 341363992 234231105 75079663 683639780 624391764 265169060 686304227 76939693
 10 10
81598156 981287141 830123412 482457331 77554645 351237238 663827505 549778905 967488359 954617100
238752550 787656851 393452025 459495943 522417885 876998499 380725999 325140429 546151936 403260186
 6 5
18103190 37957130 22509015 95257198 7950428 16850057
57089894 265203569 184343840 282294387 126924648
 10 10
458278487 288667180 648471199 581765640 758405216 1053306108 319325955 938498114 271204268 105888757
57775135 470751607 454623764 556600014 141039336 225043834 853643640 517610562 635337211 67151601
 10 10
933168403 308417110 823216696 818565876 448948583 884328249 775152756 473034231 407137956 871269623
1302355559 188479284 644003076 138712151 839886312 235562434 709513279 138285801 858528549 643830064
 20 30
81 67 100 83 128 97 58 84 72 78 59 64 55 85 75 58 79 91 64 84
116 13 114 108 17 123 64 185 170 54 138 142 89 191 78 152 49 5 121 66 163 171 81 170 143 143 126 12 175 165
 5 4
12962215 669601415 674042771 90966172 202082930
240658326 933556803 294280580 169051325
 6 5
45936257 8169878 14134346 26323055 65863745 50728147
1904649320 4160924 163305525 839524148 193404120
 5 6
284534195 1227211727 628813225 512761241 835859363
61567950 7311163 14322159 70462813 66443161 48573213

11
 6
 7667769112
 3220361921
 6133464042
 7840004002
 11622500129
 238386210
 556069380
 4628
 1889
 2867533881
 781991027
 40738940
 5515744163
 1479270495
 8854660961
 1149267712
 10329862020
 769741424
 7564110047
 2255628086
 6062961855
 7850896696
 11095759574
 4556
 2865178013
 783181425
 5301917341
 1343402295
 8650608929
 1759800953
 10193450066
 825509558
 8
 7685456349
 7872208857
 11375801438
 4637
 2321300027
 5612265050
 8841335506
 10379113010
 828990028
 6
 7839798588
 11131651529
 4654
 2408486824
 787389155
 5390200649
 8410459903
 10270971782
 809790592
 2
 8000944743
 11097559706
 4685
 2453289336
 807244328
 5183066143
 8281949736
 9892734954
 765612418
 8350081520
 11140040433
 4715
 2353645734
 783181425
 1343402295
