Statistics

Problem Statement for "HungryCowsMedium"

Problem Statement

There is a herd of hungry cows. You are given the int[] cowAppetites. Each element of cowAppetites is the number of units of food one of the cows needs.

There is also a long straight road with a coordinate system. All the cows are currently standing at coordinate 0. There are some barns along the road. All barns are at distinct positive integer coordinates. You are given the positions of all barns in the int[] barnPositions. Each barn contains an unlimited supply of food. There is no other food anywhere else.

During each unit of time, each cow can choose one of three actions:

  • Do nothing.
  • Move by one unit of distance in either direction.
  • Eat one unit of food, if able.

A cow can only eat when it is at the same coordinate as one of the barns. Additionally, during each unit of time each barn can only serve one cow, so if there are multiple cows at a barn at the same time, only one of them can choose to eat during the next unit of time. Each cow can combine movement and eating arbitrarily. For example, a cow can move to a barn, eat 2 units of food, move to another barn, and eat 3 units of food there.

If all cows carefully make a plan, what is the earliest time in which all of them will finish eating?

Definition

Class:
HungryCowsMedium
Method:
getWellFedTime
Parameters:
int[], int[]
Returns:
long
Method signature:
long getWellFedTime(int[] cowAppetites, int[] barnPositions)
(be sure your method is public)

Constraints

  • cowAppetites will contain between 1 and 300 elements, inclusive.
  • Each element of cowAppetites will be between 1 and 1,000,000,000, inclusive.
  • barnPositions will contain between 1 and 300 elements, inclusive.
  • Each element of barnPositions will be between 1 and 1,000,000,000, inclusive.
  • All elements of barnPositions will be distinct.

Examples

  1. {3}

    {5}

    Returns: 8

    A cow that needs 3 units of food and a barn at coordinate 5. The cow will need 5 units of time to reach the barn and then another 3 units of time to eat as much as it needs.

  2. {1,1,1,1,1}

    {2,3}

    Returns: 5

  3. {4,4,4}

    {4,2}

    Returns: 9

    The inputs are not necessarily sorted.

  4. {13,6,15}

    {999999994,1000000000}

    Returns: 1000000014

  5. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {167,33,138,18,56,67,77,108,102,176,122,200,84,100,85,12,129,97,76,51,165,46,4,119,170,32,164,9,150,50,179,189,16,60,80,197,43,45,22,35,41,75,15,132,117,142,38,36,131,180,74,141,101,19,68,191,87,44,34,156,82,83,128,114,98,99,81,72,121,79,3,94,181,157,11,58,20,136,91,49,144,110,103,137,111,29,153,59,13,145,47,133,93,10,184,95,92,1,62,187,162,96,23,198,14,130,109,88,115,55,125,126,192,127,166,168,149,40,52,30,159,195,24,186,89,199,25,120,61,116,196,31,173,178,28,135,147,177,21,152,86,53,172,7,17,123,48,104,65,146,171,78,113,151,193,183,73,118,70,174,106,66,185,63,160,188,105,107,57,8,69,112,124,6,26,64,134,39,163,54,139,5,161,154,175,143,155,158,194,182,148,169,42,71,27,90,140,37,190,2}

    Returns: 25

  6. {21,30,72,24,70,13,34,51,74,69,27,83,29,46,82,97,75,57,77,6,18,5,98,32,41,95,4,14,54,62,59,7,78,15,84,28,96,8,20,94,33,65,71,42,16,53,79,90,80,81,50,55,40,25,56,48,89,11,60,76,26,86,93,47,44,37,3,52,91,68,45,12,36,43,49,22,61,38,66,31,58,19,63,73,10,17,9,99,85,39,67,88,92,87,2,23,35,64}

    {36,31,20,54,55,44,56,29,43,84,53,30,4,70,15,72,25,49,34,85,18,93,73,90,16,19,5,79,13,9,23,39,83,52,67,40,68,69,66,58,57,38,42,2,97,21,17,86,48,65,89,60,28,82,47,78,50,81,8,91,12,3,74,88,92,77,71,80,45,76,62,64,75,33,87,24,11,46,96,22,94,7,32,10,95,26,61,27,37,41,35,14,59,1,51,6,63,98}

    Returns: 100

  7. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {999999977,999999975,999999962,999999988,999999968,999999976,999999992,999999961,999999998,999999996,999999989,999999986,999999984,999999997,999999964,999999994,999999985,999999995,999999971,999999983,999999979,999999966,999999973,999999991,999999982,999999993,999999974,999999981,999999987,999999970,999999972,999999990,999999999,999999978,1000000000,999999980,999999963,999999965,999999969,999999967}

    Returns: 8499999981

  8. {999999947,999999986,999999799,999999940,999999922,999999791,999999752,999999957,999999935,999999790,999999992,999999805,999999702,999999853,999999804,999999851,999999959,999999880,999999725,999999931,999999710,999999718,999999919,999999916,999999870,999999802,999999899,999999934,999999960,999999729,999999762,999999811,999999782,999999794,999999770,999999892,999999767,999999926,999999753,999999842,999999862,999999944,999999978,999999743,999999719,999999860,999999962,999999835,999999984,999999948,999999975,999999789,999999779,999999855,999999709,999999910,999999775,999999939,999999965,999999925,999999806,999999837,999999747,999999972,999999964,999999822,999999872,999999938,999999928,999999755,999999996,999999744,999999929,999999856,999999841,999999852,999999817,999999893,999999968,999999836,999999883,999999999,999999918,999999937,999999877,999999971,999999783,999999876,999999886,999999807,999999863,999999977,999999958,999999732,999999989,999999943,999999885,999999750,999999813,999999857,999999988,999999798,999999816,999999796,999999909,999999716,999999703,999999949,999999868,999999983,999999785,999999981,999999787,999999717,999999873,999999889,999999956,999999936,999999903,999999906,999999895,999999735,999999819,999999908,1000000000,999999754,999999976,999999942,999999917,999999979,999999887,999999874,999999763,999999896,999999904,999999756,999999761,999999849,999999712,999999864,999999946,999999990,999999818,999999793,999999795,999999878,999999810,999999966,999999766,999999721,999999854,999999739,999999890,999999736,999999801,999999825,999999827,999999730,999999924,999999814,999999833,999999987,999999706,999999933,999999792,999999723,999999905,999999980,999999812,999999815,999999985,999999912,999999970,999999921,999999832,999999998,999999913,999999738,999999846,999999954,999999834,999999701,999999973,999999797,999999894,999999733,999999781,999999741,999999737,999999888,999999840,999999771,999999879,999999869,999999734,999999809,999999784,999999850,999999724,999999808,999999997,999999843,999999897,999999945,999999875,999999969,999999714,999999991,999999932,999999713,999999780,999999927,999999982,999999746,999999722,999999727,999999859,999999778,999999707,999999751,999999777,999999951,999999898,999999995,999999963,999999823,999999726,999999884,999999704,999999821,999999847,999999745,999999994,999999720,999999974,999999728,999999829,999999911,999999803,999999923,999999901,999999838,999999711,999999867,999999748,999999800,999999952,999999715,999999769,999999844,999999993,999999828,999999742,999999760,999999824,999999839,999999941,999999950,999999759,999999776,999999773,999999705,999999882,999999757,999999865,999999953,999999740,999999900,999999920,999999915,999999858,999999881,999999786,999999820,999999749,999999871,999999914,999999731,999999788,999999826,999999907,999999765,999999831,999999845,999999830,999999967,999999768,999999961,999999774,999999708,999999891,999999902,999999930,999999866,999999764,999999848,999999861,999999758,999999772,999999955}

    {999999999}

    Returns: 300999955149

  9. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {773333356,926666674,506666716,890000011,30000097,76666759,943333339,770000023,256666741,10000099,783333355,460000054,816666685,480000052,980000002,710000029,806666686,16666765,416666725,866666680,390000061,810000019,900000010,553333378,83333425,563333377,550000045,596666707,756666691,753333358,663333367,946666672,666666700,6666766,156666751,576666709,570000043,953333338,56666761,923333341,353333398,206666746,800000020,483333385,726666694,633333370,973333336,190000081,793333354,620000038,320000068,273333406,46666762,183333415,443333389,623333371,363333397,210000079,516666715,846666682,63333427,276666739,830000017,346666732,163333417,976666669,983333335,676666699,603333373,213333412,546666712,510000049,310000069,540000046,263333407,270000073,396666727,243333409,566666710,406666726,836666683,426666724,286666738,823333351,123333421,380000062,636666703,100000090,826666684,20000098,333333400,736666693,713333362,430000057,590000041,303333403,746666692,606666706,160000084,646666702,920000008,436666723,116666755,196666747,933333340,493333384,93333424,730000027,960000004,850000015,813333352,586666708,653333368,970000003,246666742,990000001,896666677,500000050,170000083,580000042,643333369,43333429,776666689,153333418,410000059,573333376,686666698,356666731,766666690,253333408,683333365,456666721,433333390,733333360,870000013,853333348,233333410,893333344,696666697,503333383,240000076,533333380,680000032,743333359,640000036,723333361,820000018,143333419,66666760,230000077,996666667,403333393,173333416,600000040,120000088,466666720,200000080,613333372,440000056,266666740,993333334,423333391,53333428,873333346,26666764,470000053,316666735,293333404,73333426,950000005,33333430,650000035,693333364,720000028,283333405,513333382,60000094,176666749,220000078,393333394,203333413,610000039,296666737,386666728,130000087,986666668,840000016,350000065,186666748,1000000000,486666718,326666734,330000067,23333431,860000014,300000070,913333342,556666711,626666704,560000044,343333399,80000092,400000060,226666744,593333374,70000093,106666756,883333345,790000021,313333402,446666722,180000082,413333392,40000096,833333350,690000031,543333379,476666719,956666671,216666745,803333353,103333423,796666687,863333347,740000026,323333401,963333337,910000009,236666743,113333422,290000071,750000025,700000030,880000012,530000047,136666753,780000022,903333343,146666752,86666758,583333375,886666678,13333432,140000086,523333381,760000024,473333386,376666729,90000091,110000089,496666717,876666679,50000095,306666736,490000051,526666714,656666701,250000075,370000063,763333357,373333396,856666681,340000066,673333366,366666730,150000085,166666750,223333411,916666675,260000074,660000034,193333414,906666676,936666673,706666696,536666713,133333420,616666705,280000072,453333388,126666754,463333387,930000007,420000058,703333363,96666757,383333395,520000048,716666695,630000037,36666763,843333349,786666688,940000006,670000033,336666733,3333433,966666670,450000055,360000064}

    Returns: 1733333360

  10. {7,9,2,11,19}

    {36}

    Returns: 84

  11. {3,17,18,15,2}

    {26,38}

    Returns: 60

  12. {7,7,18,3,19}

    {11,7,34}

    Returns: 36

  13. {14,11,7,7,11}

    {11,14,34,18}

    Returns: 31

  14. {4,3,5,12,11}

    {10,25,48,21,49}

    Returns: 32

  15. {879870650,617147050,824637987,837817103,675981191,780769317,917247983,850429474,667623320,573971367,569496545,706174059,714535085,830360688,946676992,515817080,999617151,800377338,822019399,734728419,558348560,571931908,821128383,663430449,510955141,663164321,814255249,600226058,855219360,652069954,867440247,709313661,843287572,518576436,615486285,874915809,633232222,553826628,648493998,605753623,755235994,940983223,585509640,519242573,984416744,880021242,641053036,693576786,536689435,740483489,693189904,951494619,842944045,882016757,873898065,532516536,541519439,742196032,730271908,589819341,629417783,886842568,997144252,743320916,591040082,535890889,734695141,896861878,853631072,771329586,746207211,902046127,766461349,978244540,748841761,662066365,923021785,520376877,731283737,880134574,696797914,981286671,960215180,844712001,780157769,530241658,559764104,823188343,927103275,523821727,697876846,597123983,850128560,756176781,861585001,956529277,614553826,853474017,584941912,658831163,624342044,903437493,876134075,691401636,974648868,607635417,536031452,577609315,702024564,948009005,878590446,824211241,965277173,785832495,828074653,645413966,911235158,991897239,872754323,937644634,693114742,951505893,508461577,901046423,779793507,624787583,690263855,685903257,875970576,590969832,638010268,582119223,693540487,820325711,893625196,577137047,718810918,607883668,890912712,700506868,653845142,935046512,531499996,921765626,831301812,826813103,546172068,871236067,946979156,922045294,794830416,528908419,684533014,772220000,648961136,764007624,560541467,584148532,644725175,955678518,895904517,766199744,880526896,698521128,818927845,993262073,733892006,790261420,827769809,985814204,729263963,516640943,541318426,836576609,677615919,698582259,985962938,564200212,793581130,625497885,665769518,579024985,982772310,725204768,762108877,712570351,527782134,504134863,966812583,744146978,655577672,966046065,728301876,977387080,968154704,754988475,585621711,855033877,650827277,762888784,944716930,571644887,539460283,952728259,761829466,800453048,944310270,787403350,813391816,839410200,662900798,924514500,768700646,709502786,762410947,976437243,795576779,643056367,701564105,789207269,653160999,969179421,822031270,882725878,697559409,583563237,761080766,841867766,664297679,645066828,801302162,848228353,848585283,952012101,670722334,990824689,731756235,825301035,634774529,874023570,819409132,910097084,735927388,776437357,541200478,889177219,598331061,798413839,535510426,923285137,931928395,513442358,927810497,867045318,741736835,774611843,510330849,680224994,525990209,859257015,708948622,527622509,502963427,646446549,544159326,947443468,590721851,814373160,938004004,671581324,774092491,594142262,539632361,722495438,794789679,506018620,930164106,687315631,772762473,505181651,573574292,631927937,865179726,842925457,549271821,797891989,501293653,599217609,789919280,673424803,586330996,582770336,634393511,833720846,664077240,904335896,971182380,739698894,568652177,782641736}

    {882822054,958508567,729590294,610423750,620270715,595672255,742434626,826386370,616045277,541118512,867416196,721267510,670647131,785796984,822541492,759204796,791300657,535377698,831470433,824066772,773663986,985883441,529392525,780125906,570290636,871583770,567181902,573833687,988424400,987200730,671206817,608684018,781949756,971683041,875676174,947971803,872086476,970327768,750102908,590678450,862905436,688440934,681251363,779125985,850405932,918105804,603200377,733406016,602952782,658456710,556182512,608312286,800476607,958068230,934361642,702155012,976701607,521040258,770509494,615055001,661753446,580682633,835134286,963025142,781510401,968428264,555478111,846258609,529695688,646379599,579356092,862338437,745893555,917950979,605569313,835318060,830086384,806338780,851801487,624911073,714504777,832336617,891994557,980170314,864571863,605078682,987723539,528731184,738489174,546731234,981844598,519081502,741736537,879006240,690876526,767451528,962479113,742476560,702541770,861313797,557008480}

    Returns: 2973590629

  16. {931383294,552665068,996769874,696962455,801667056,742874653,598420683,934156271,821807079,699466833,874465063,870912289,800023764,721882384,575848335,973264627,872281371,609756290,535919299,905619879,572881691,708007832,889195967,840451250,775497375,962608525,831122770,767578193,678974609,730582160,890813314,527961318,902900515,523556239,995484562,973957713,766164524,776645687,763224683,940941805,947825685,635438930,726770578,763061541,574378839,741107821,683870024,778937894,857816077,772460947,579365888,870916545,866893864,960441183,551570786,603800339,709517519,511635037,575504616,920886521,837561400,533136621,822447243,846141901,770697710,618372932,684054371,875372589,832261671,644668450,723859579,685657144,911401592,987972679,784623289,517037003,900492789,749873849,795933751,537796510,627770343,967902351,865404811,623949723,536041151,950085480,966844831,751404140,952374128,584474182,714305949,749014178,872363860,915812108,928187297,787550804,570210220,892718920,866379626,978575298,901440810,597328925,517528840,555528561,813242197,970936420,567237058,515439055,936244528,828741864,812186779,762906019,583008933,596160230,926325625,995086132,592704043,542331088,522706704,731048154,747215961,963918563,841961666,511180816,825479195,987088762,663171915,739017904,858344937,556230904,780834346,616117478,752131386,826158872,872794233,863984299,800412087,960535459,726398162,635108368,691134524,702125355,612097615,794031973,732682050,782956701,664466911,545360322,669673774,844380094,582351282,908039220,899034689,827128970,728291282,751794276,761763084,659165588,511557925,713509764,948678236,604667512,820834422,504400472,927428010,933188157,715905637,545369210,600711473,534138548,543069897,601200289,852967253,805959903,746853553,759483465,777808933,800002764,871975855,689263303,823126505,559619637,595777064,815043401,636650944,626745487,831513159,888420671,554579246,735894121,619337280,964582353,852076457,840619333,544212649,994449213,992969884,561345226,517916520,559801897,687239752,677637127,868008909,656089570,979841789,803975193,891038701,784239003,528747724,861196148,584721732,567743379,757790280,895100921,605709364,634566181,574338325,853141681,686413137,625704608,733319891,637183889,544944551,724042199,522508959,725628712,546162285,611241378,670190931,649093935,892152284,562280943,700648410,591549620,676694816,611048166,897506029,629032738,718632991,627739117,522234251,711372386,712598831,750224171,970949023,532381900,675630280,930848718,902596383,747521626,769356110,715585269,977981337,744885488,797139583,659105699,670082079,724112245,928976016,695638136,850607021,543638937,814550512,528058490,635669485,667197177,671399462,757990544,806571339,614020446,687843127,730222733,756875315,887756224,837654029,946228181,869487272,700821290,732565220,867916921,688915863,554215001,578948258,807908731,501633864,529215425,768931671,935840868,764250108,521624345,610348528,593251088,706395109,722902732,519224523,787419514,808229467,774524420,756879558,673506128}

    {947588558,849484443,993350976,833040271,686705850,713016349,706575948,947133320,798730520,956872192,957675226,973410435,968516066,736558046,921312837,925456329,676592896,729324653,812531555,773621790,847612856,800273889,738693270,966228319,964143801,721841392,882582510,807044681,725744468,856114199,730675734,904664533,778991312,750141961,834198288,887168679,853772693,978219710,858410817,957686097,676456343,862637133,939605587,865005413,731212221,704632023,872937836,684910755,927194698,769827269,960127869,939577725,936236997,994636652,709755383,760907478,898616283,988053686,742388654,896329756,712468556,744023705,878262940,896180981,876647150,911029915,669131513,953818574,669594403,844515692,873158630,970237829,676497360,750076755,841804819,849916479,760379207,966025639,777671659,929861399,892454406,901481534,852445905,690622509,899555775,686131434,834787749,937902458,937382950,962344072,669195131,784578114,811270206,966625553,679929316,737357925,717979066,814677811,856646473,848710388,720299047}

    Returns: 3031838843

  17. {577867802,891470156,627267549,668878313,637347378,641702595,533428775,529336724,719392432,814425195,774378211,621775064,647254239,723666205,721515825,545539050,909952008,982189687,585554096,500753122,515216165,866189629,518260651,705564913,519450797,555612228,876449879,792731981,726241574,910412667,712842774,748087038,681317293,743611077,798761403,765109576,715760021,675028947,968349497,646149132,908221130,852499253,729263001,641719549,543232683,578814272,765280981,699933637,820914499,580061493,522794029,937425157,709912940,749783758,943021825,755141866,791779791,622197301,579346697,842321253,859702325,817354522,715603776,664185685,793138414,734018578,661212196,653998122,614928387,588214033,859199806,778896042,570708977,518510680,717133902,554337140,731847165,828016203,878019003,874794695,928529436,554447251,654173119,581886771,594267416,523059004,656294407,982348801,760763053,535546370,541842881,920337200,802600833,699404963,961164583,608158384,770868409,740581307,676675192,868524939,621379128,558972596,787275511,614409286,994812992,864805443,909950535,967369056,686728580,584856789,827689873,691792227,801381937,743319857,508098275,706534350,536957164,836913127,582961667,625332827,605790441,801738289,517800201,736156001,902538129,585988796,652153327,621246324,735624614,660543518,708233820,768057573,519879754,872016414,502308720,693492898,770598322,846147444,716142400,532653870,792956957,888395432,629262957,965929562,561392870,509765832,713884065,515525528,957357142,877821199,663671597,898847454,866804250,774798846,511175311,874626360,504558053,811105529,586550042,617783337,544850720,859676498,576184825,521027777,965174134,910383004,923231741,786364913,528706371,740741451,923799078,915285300,738805752,960274691,916604431,600229718,676363722,509992880,821170471,833740183,769461119,757574767,654760822,977718218,969452854,907939845,990529090,558767556,963956015,749830512,899926476,607451109,946761583,994748280,922049563,649566812,928756628,871098394,552214509,692395554,919403688,920718552,766899862,714707818,863970845,698931767,544046358,838188247,700145196,907071127,813795776,624014296,914044237,824081131,977733741,954953444,606491694,637688253,595752717,962336349,611734539,957905392,791527494,811109289,890437705,510340016,671712341,971900273,911256727,805956265,867598006,761025526,648576165,647239348,849908374,537139924,793359558,718733844,815455715,598896884,501560315,676251620,820571896,548535889,867250808,951845601,762605578,785247845,551322242,757638276,770251585,821327339,949127813,698797424,555976746,595915580,649269480,823998044,878934449,567304663,806884925,628866555,997377777,621892028,999754134,583257707,508395900,640220194,756534006,770214549,984551947,996597321,949139711,780174776,848941856,965199088,577722131,615439633,899958961,866528835,870746445,559077488,548562702,574798018,716568910,769094888,819898292,565131705,502701229,636899953,796236007,984788823,837248307,728142048,572946000,609457610,615757656,774472864,788886952,906880670}

    {872699069,964373130,822606692,814255287,944854145,926985941,818481983,915325709,891080339,856090507,767160754,829954999,945239823,754679220,884719815,816212137,866018445,820848506,987988004,984142034,864724333,865676978,979714135,771293887,752062280,850053617,839627443,941621253,999078715,794253335,876479018,842516413,926060879,796537190,840885366,809865457,918345527,752130235,909108432,865841027,881409259,750694979,882271156,964568089,752879130,954024868,784247386,893831007,957193295,983043556,810590425,905267987,855347243,761866069,995535677,797914540,782801538,988274997,841538546,884882739,753076887,879232352,782584058,801621460,867265244,778288654,957151026,867524539,976389393,885779002,830741910,813859925,976569477,966685337,855508926,947254529,790090624,972637498,786540925,805721848,964097708,939192457,903845878,809396284,955087563,924120590,773134481,838333532,847801520,917860444,763036064,896017635,802663811,922832508,935864021,770734630,809971479,863159325,988991717,807886231,882432615}

    Returns: 3059103579

  18. {513628244,515307199,781871663,690216316,582978955,502641774,890461450,766313332,665927959,738242958,649004332,826907561,869966493,907567265,961974836,882613572,779960625,742025885,666908415,737220718,987784983,604752692,932540886,806607476,932906206,596987370,827618147,736959847,579637773,737185711,958872020,675604374,617876505,782237463,659276524,788648295,732095439,631552598,826276007,832586569,534167848,866260668,545588165,503951628,838492988,558811462,838827417,985916973,968679160,675637582,664753355,591806376,897506892,883538421,804903521,756149994,902740165,564317612,504754592,640055633,518320920,916610124,591918126,779077957,680983860,762645379,758561818,670176987,876164417,791314606,716134128,688688411,847180649,595718141,716093968,741895772,677994635,619768250,506037085,671813397,653174271,557229482,527255060,828467483,512514180,571348889,783323508,872982089,743778984,519704058,641407611,554732313,583811440,791011232,635039337,621318420,651647212,565604608,970989884,547394516,551956736,936956788,761506239,985736602,663399765,569451769,604260241,823010974,725173183,901578219,984319122,892889858,981427149,861429766,645281636,752860534,634261928,507308397,875039466,507664692,872135942,931888334,900219725,603343940,995794941,763165670,927276508,806007235,958897832,957589552,783393660,657327027,980028360,877269513,829261482,515076332,609241195,910679895,739491347,885562772,759959411,564664221,788851056,914679167,599087909,959803207,601470053,671354920,914143319,840992954,879364795,824114235,734856308,612333414,638033269,858144222,742079621,678359986,955449475,905974289,828469465,522126269,628299305,504645860,560591237,797185665,633899849,563949989,669473639,802576683,539432420,856209321,945983237,678136423,593743583,831589461,878547216,552461844,528570967,818008873,822073293,717071184,831537643,934766985,901497239,579110928,834959062,598959764,690142196,872024462,844821310,868863607,631065389,621231233,592065780,624363371,735428991,810263372,804432327,561993757,679301981,692826248,730487149,789845036,800286120,696315297,554185253,666221810,866237854,750184055,654017995,555180110,719146259,521058735,591912220,684133203,881169091,955482363,780028687,697424825,992600840,913297058,542454863,707790603,805113232,560141789,907524466,532774568,678309085,947190273,725035481,828961145,983501485,645601238,821987899,775947851,673001303,770373546,843280817,737511891,802078223,562060859,725310641,635529610,533897462,770329260,935422288,796891242,915691678,969863148,611566159,784983698,538318913,666193292,700252366,763358026,638722960,678807627,739116168,960012145,925560828,776071010,836006581,966878286,847991878,566362501,702944907,832091124,753773801,920149448,554422536,603772363,868255566,564454192,907832189,634542978,888674985,537478603,646917316,817122911,680828852,676087320,735383695,819591296,536916032,758662264,613978392,535454917,837563257,595229680,541346056,848315886,888657015,622056552,893080578,944100713,579075791,809835972,911535156,902585019}

    {846044104,801210744,966395734,977238874,810015072,848940087,973003848,957499675,866338154,921279008,923304757,937575931,817358255,905206585,836621927,992497777,910081966,814402839,904560179,989348246,880341041,914618035,910897643,996416183,922424554,802204003,888914530,912791818,943473385,948412870,833918594,860516189,855691145,940462349,854619559,909112782,968426091,935417103,812083242,827392701,900214142,877664012,866738303,924773319,865345597,857789179,848515328,881826829,958879634,967301773,941863031,948451403,918699698,856562409,914086667,904394037,899276542,821957046,812031005,853048664,837725121,980256093,995126517,852614109,879040228,881482102,942549157,839285725,844706436,988992913,918727950,828529557,947759807,984388717,839408607,857816023,963098844,988429500,950086744,956170250,952119527,994613032,846204186,874148790,918739873,809160573,975216584,865950638,814447154,941670649,940587647,863442482,878164973,805388920,891817683,852805179,801880335,837232966,932103369,988554800,931127845}

    Returns: 3093324547

  19. {631198173,627183544,680424388,832413126,681208084,649318715,517071514,938217216,872028596,764074265,538793938,757716496,661258603,546828189,796566535,608051320,669399200,662106979,633922262,789060211,664600624,752035775,829744435,948593244,984859172,698453452,982922235,755683181,868799956,768617925,545657288,710253867,985543826,696491453,609566823,618469259,555595120,530913395,720275193,682250679,748039648,823887848,960458710,911325935,902882443,506450663,542852932,738619639,710790747,748919387,906843491,804662952,808093011,960054303,735817883,605359185,639627951,710047657,913511312,760726226,711913861,999710323,687517347,628432195,935439550,747967101,589768768,758513518,702262813,601196194,746745432,860739051,898398205,842246142,724500673,707558701,679022967,627826097,500902239,710253961,535652828,632851639,943073461,620126812,983105627,873945732,978263588,824375308,738091446,573598727,514364181,799761477,871632189,575042004,639443587,976279297,946897049,848966100,547905968,977245009,517271965,916843850,835357245,719043162,653302773,992223292,765646785,740323859,789870899,855146684,544263889,994592067,969737310,837701019,795152200,707986811,573132120,560083380,702035131,658964949,971425108,861530691,654743324,859503205,847360546,614208061,766338615,978497855,566444807,740422411,978050154,903987144,875963157,627364139,809264703,925954241,671006373,790551972,915401414,904363601,527817895,504378877,720225051,679798670,739314260,860838326,786945358,953303007,500764782,570175899,605913224,939513971,557626381,528356285,953708870,995379728,982794002,925943998,577102682,876625607,544503961,612942952,869911399,676561659,774525145,730737256,743212316,956433873,604992412,758246106,617143036,585842970,891598042,837457393,911238747,948336597,861009269,831954123,510646057,714514260,625734643,513069609,526577116,572927959,869118261,747801228,835815619,627876047,662021421,630543784,597335345,914943117,818722815,788974922,767802161,917194240,649011879,669384310,508125744,575594041,682239520,797636916,808818995,544843332,752772859,532146284,631422418,665630571,590742928,845834878,860520358,853542805,755505682,634299151,721380695,920179580,862437519,621142072,555597259,820738213,903873062,951500051,849373681,917739718,576275332,781557675,660622256,655385651,736185489,591667812,704874600,713597134,626101405,748565900,738620879,817629604,799513854,542939156,642028246,560444348,744781948,931229685,577835073,702977824,508154906,656060586,938728676,649110526,820031523,875423724,814634171,754238079,664509676,512737649,644441535,809488837,683294388,688405110,913003911,868353108,749210165,616129852,890723863,693677828,519271876,531003682,764270555,630595118,923611510,885495952,995861983,778178774,773484032,655186664,718362967,706277064,566164725,724849639,986525953,774654179,619210556,559069465,738323872,553489099,818052615,621901901,734154362,822951034,769717379,773028595,728935408,779544945,694691788,708867982,755108851,591177408,858906758,693575438,698462438,717417402}

    {894096241,884456355,858901135,864928208,955393687,930693159,912443492,913133769,931881037,935009303,927718581,955582038,856437506,971927613,834436257,874041079,975239998,876436306,874647236,947233840,992944555,878271181,908989986,995802957,952371968,942898006,999868304,885310429,909885847,895472590,979009941,839436475,907385291,986751193,836172966,947173844,955486805,936976114,921379038,884168521,926372346,842242095,848034841,936828589,851955954,951294448,859457550,870447396,949318659,914001603,874007280,866885104,928088970,850670958,923873324,979149512,873968042,874482310,841287206,839406068,876865088,979777032,898978044,884415451,882452744,999939019,924055768,942977447,869661220,895180832,837501916,913059949,931358057,854813437,833968601,844633079,913977935,918784180,839436785,936500557,896668325,946213611,902873697,928362486,976225259,979552403,988814199,895471641,935728821,941596712,861573018,883850678,853886488,973905905,922419132,895998829,954371856,940093525,866663290,845300462,867098582}

    Returns: 3107577333

  20. {262456118, 719336917, 406770033, 366995731, 276744176, 319439556, 840471386, 52744931, 439586055, 635918816, 833058215, 327632184, 731458678, 3746435, 879100887, 385868509, 56250466, 15682725, 780728595, 690016516, 141261971, 860542141, 326557716, 478273023, 266372689, 235385699, 447779465, 108902997, 576317587, 550062721, 907658909, 392078509, 341643035, 376724197, 641417596, 723516424, 368454790, 286041530, 828941498, 812953555, 414239425, 119592533, 595732347, 468521016, 580447629, 219036190, 99914318, 691822449, 337614464, 335363318 }

    {555931, 116229, 386714, 855102, 56536, 429755, 889924, 780785, 301748, 624644, 683976, 335157, 612537, 584161, 843958, 627059, 915764, 275039, 756650, 656557, 356204, 689086, 831082, 422764, 244526, 349384, 345673 }

    Returns: 907715445

  21. {107429089, 922076081, 550591552, 742236985, 751842239, 350913769, 231505915, 477724005, 511117020, 552824576, 159126381, 556958767, 970220523, 69755965, 79019548, 207879232, 254287329, 640212555, 288797199, 675227877, 952081275, 860679354, 233316948, 91420305, 456086966, 854592382, 991742331, 828650841, 227993173, 128955246, 919633946, 343303030, 702522974, 27684039, 552264519, 943851463, 83745949, 45409190, 662407969, 903781453, 254737440, 213137041, 989712711, 202999981, 473559737, 532946159, 714418015, 498904241, 330336127, 42125195, 676429201, 399211207, 154093902, 400985365, 896153865, 69621888, 16728898, 562289825, 914537081, 701942547, 40009024, 700792871, 803697812, 389864920, 331363949, 372305665, 701371028, 12785357, 116881333, 564621423, 16606389, 790552852, 798384197, 50824214, 84940984, 25502579, 649281041, 561403517, 11152481, 704159955, 993094736, 848359311, 298137593, 360561857, 167428603, 683276573, 736752332, 167465968, 44746321, 190070617, 671744940, 846726325, 970010966, 479952219, 12785517, 955630474, 623355471, 736456607, 916129639, 212809099, 668780103, 266532485, 474124279, 274307836, 147651725, 148719824, 181704446, 811878849, 912267060, 184071720, 41564257, 557266917, 919119250, 812874136, 414391943, 91657748, 4318914, 333814800, 277288158, 10792992, 961562658, 310470372, 47411798, 392665471, 553939925, 911369803, 814005732, 968987596, 523759426, 142506978, 577871617, 492293442, 20086675, 193364262, 899322920, 28268868, 66279992, 495221245, 258652507, 34043096, 140578657, 40621870, 972398239, 328765735, 395857031, 373999845, 674934396, 735505918, 287594724, 663331120, 576824446, 246301776, 651845109, 959104644, 436081590, 80085170, 85652991, 755578424, 642547001, 968887774, 588171912, 370939656, 678557344, 41332529, 988398298, 850615188, 398516359, 188705580, 707347076, 246969567, 905063695, 774407671, 970291160, 233772241, 728479323, 826018777, 247413358, 506888374, 192652566, 750578625, 29522335, 298251196, 10118892, 426189249, 537148171, 561025400, 548058380, 112423309, 322218260, 383871073, 691579565, 957427968, 835563872, 517899348, 599518086, 808231576, 928101211, 59248910, 835967572, 355098613, 613367475, 244878518, 25943896, 283726942, 131949018, 329484880, 697810646, 172148540, 761104519, 576128075, 764837783, 206173852, 926706229, 549207796, 709943656, 344703409, 502106275, 225688320, 704177049, 156164944, 410173010, 704231431, 543939455, 399817843, 747887883, 216352515, 258939634, 983084727, 656759894, 472247509, 318023376, 663717598, 11128324, 793105600, 357989752, 644380493, 261660326, 430478060, 731442511, 248226446, 613683219, 483194596, 430635839, 782054864, 917605350, 42626585, 50958131, 406459234, 968306685, 525530717, 688417948, 414780732, 32777979, 14177896, 319022319, 371928950, 344082119, 709960279, 111960613, 366713550, 528793356, 984381991, 709045049, 714075943, 443111351, 585048127, 879948974, 180733444, 237518716, 102648292, 143636230, 251084049, 92400208, 666287042, 987272524, 400003227, 625147888, 89173097, 18549131, 479446547, 746576473, 422491854, 821681493, 554854031, 483955790, 74276038, 673274941, 338970953, 179808214, 557914510, 76766813, 370503198, 361733307, 27277894, 115281105, 642410512, 136201996, 998605426, 33649210, 975296452 }

    {548050332, 522455671, 932991292, 988149253, 21459072, 26913828, 473959168, 739814975, 135210901, 389047590, 61117874, 968313093, 258502904, 489140115, 887915268, 779724427, 373421964, 403171424, 652514986, 303008045, 274037111, 3909098, 608398556, 795176934, 510031525, 569579121, 401158359, 48169177, 780300100, 727240345, 18932572, 278692812, 71381574, 182153192, 266252592, 582413480, 688176099, 929565002, 687954330, 796947963, 70755348, 105399184, 311502056, 667306870, 462429465, 761058284, 134310634, 756008047, 994935283, 761462390, 913156469, 803090016, 108655851, 607070379, 551365345, 904669030, 791154185, 116620265, 746634380, 141494467, 381032862, 74979316, 351434069, 173433181, 369845947, 258102644, 141954082, 915013692, 769205687, 275748981, 742145626, 103681807, 517723821, 12104421, 144426603, 54817448, 706201596, 737072921, 492298822, 687110012, 958244037, 446569033, 500984286, 767473700, 776377200, 611157775, 360805805, 499768287, 485876776, 710688748, 868586798, 521768717, 702140250, 956608964, 9770340, 57558965, 321438778, 316331613, 948164434, 109072384, 551929662, 577504995, 286275201, 876798140, 25204385, 346152551, 618889085, 925027290, 874453729, 452799579, 135231064, 239580913, 483463489, 366671640, 72412453, 735208888, 685411912, 649072216, 28549246, 991794319, 485440064, 709733820, 20813311, 251585271, 822925752, 454897480, 657060041, 939838998, 414850051, 459492834, 388450304, 45693749, 860486071, 662534102, 580845389, 501092929, 605430575, 807645525, 109614429, 682715213, 314998537, 480806641, 994636896, 690600461, 327694504, 892833827, 820676747, 708327005, 928439986, 890732997, 862283414, 34085048, 70521235, 82301080, 920158783, 4101058, 359612921, 484631488, 198210757, 70929343, 601849687, 253548355, 998232941, 995385625, 908416610, 969068174, 201725440, 119540446, 955072407, 559830767, 749473099, 195707199, 59888562, 856709659, 170125727, 632977427, 711150648, 785719466, 181031247, 152136018, 987348463, 969106583, 853903156, 111800218, 132459360, 407565249, 820420908, 989425837, 539087196, 276095596, 296210070, 607016944, 297254772, 874925504, 481177304, 544383214, 446215808, 324873801, 409417690, 338227667, 12556057, 376519286, 913091720, 942556658, 309518366, 5560602, 666936147, 270116928, 243350835, 416523246, 420420785, 142409175, 881141053, 54112268, 384805273, 25630323, 25575144, 580264566, 438444552, 659425528, 977506593, 670301837, 3613054, 872466922, 526642588, 815844506, 298995585, 36903411, 834876239, 241990217, 853697049, 152579681, 548260597, 494700328, 585857107, 643573157, 96006029, 110491437, 658419391, 342344150, 218315992, 693261614, 47874033, 144323372, 91737566, 778650982, 446917379, 965767813, 420047721, 32122870, 27994642, 224242659, 754272905, 897534818, 762116284, 802306284, 704895758, 179056400, 302770857, 280374120, 751150609, 621794765, 647418367, 168683463, 500644972, 614541383, 289879532, 777342873, 840807741, 670263188, 2363168, 53064212, 319339623, 913420202, 256561232, 160106641, 785527057, 312674788, 421570740, 806710543, 817681445, 879136644, 379723402, 357034159, 559318738, 724999211, 697918353, 868351030, 783751435, 677875810, 880473486, 471626894, 482355206, 828875797, 514131147, 455738693, 492604605, 972966163, 10545811, 137949964 }

    Returns: 1000968594

  22. {5 }

    {1, 2 }

    Returns: 6

  23. {8, 1 }

    {1, 3 }

    Returns: 9

  24. {3, 4 }

    {5, 10 }

    Returns: 12

  25. {1000000000 }

    {1000000000 }

    Returns: 2000000000

  26. {100, 100, 100 }

    {1, 2, 3, 4, 5, 6, 7 }

    Returns: 103

  27. {110007105, 913798797, 167171145, 951913970, 35715393, 592713284, 144873904, 377172574, 810122628, 811766477, 354914736, 638803076, 725764284, 10013011, 576197248, 319668673, 640781501, 774747468, 235740246, 449834572, 781151559, 276512703, 242790896, 81691424, 674497179, 780329275, 114173508, 5561520, 314242539, 335277734, 212430494, 896013045, 19756435, 688431535, 440316116, 289814375, 375180064, 536676549, 176735025, 760322253, 512233794, 957911347, 844003746, 552144616, 227704650, 911781536, 358654607, 219755210, 454551974, 447302045, 8013083, 964664852, 324922637, 344450806, 882436950, 482724482, 94178834, 755407470, 666775194, 534733308, 648754482, 429377180, 985003471, 515504728, 523292346, 89010893, 455717156, 59677147, 959582661, 684538838, 633490061, 763233374, 512707439, 179802103, 154557644, 556551156, 310198429, 742922330, 536893084, 653729129, 207910443, 394103542, 138462263, 311043414, 192156351, 741680147, 197127547, 910392011, 845193676, 610879726, 655778750, 206613703, 696559678, 429730462, 39933677, 211033215, 824651324, 758819307, 898599591, 358584127, 606917843, 428880777, 173141398, 198946847, 677764307, 283167008, 161860626, 332873956, 599707502, 75728964, 470237451, 896914209, 691688301, 502277556, 799636326, 497092117, 922349068, 418419698, 401915621, 365744948, 478501438, 238808655, 19863354, 210704030, 1361706, 62386604, 205541696, 390515446, 989292297, 277652913, 943789745, 718734046, 400218126, 686785098, 896021468, 809753552, 810901037, 184480956, 338125420, 915521509, 949591828, 4179179, 737589176, 452981891, 154498745, 547315481, 644206187, 514834208, 543727234, 268471654, 467903322, 28782256, 230281366, 249078073, 356285638, 106537016, 915684761, 241999687, 922507370, 168289308, 962156499, 773291812, 756702330, 207489457, 338821719, 139931190, 870388904, 296778279, 472139002, 63035479, 925848744, 96411096, 526033912, 26371951, 662283759, 395164438, 405192889, 161262753, 446303039, 569736909, 404376535, 576001403, 536461467, 752441300, 14588579, 993438448, 834212110, 746205372, 827807171, 12130551, 372488712, 313577413, 605532060, 612227979, 172649684, 255981451, 313991809, 185466291, 621730415, 659182441, 199569973, 229804944, 171895473, 833323683, 632740652, 278262668, 150336833, 180499154, 226143844, 153272008, 717464799, 95017613, 741415619, 289509656, 95727524, 46121719, 892215711, 878655587, 865906429, 813657902, 923096179, 710233805, 587528636, 639565359, 597647105, 905392127, 380412269, 729342188, 349886911, 53450464, 14236847, 11643615, 735392879, 594892974, 429360352, 975238476, 204143037, 79825289, 247851180, 903989401, 255244825, 804111760, 609456584, 251841148, 599796249, 238069375, 643507523, 22606652, 570767583, 171835632, 867575684, 246153664, 788723587, 493645459, 744720120, 816871250, 712561987, 199385834, 43157350, 615990807, 708921614, 969037720, 728725103, 213785665, 3798306, 20947981, 28883519, 879651235, 617221433, 937668215, 381832465, 452587715, 67386885, 415480140, 776647664, 903959986, 663555688, 553550638, 105185173, 368043092, 845914932, 922417360, 598310362, 599590373, 658590859, 821546994, 309877363, 205808866, 478119401, 625153993, 385530341, 452972060, 767606101, 863215893, 227748668, 877003027, 402077594, 984188516, 457431201, 155559683 }

    {664318054, 619451937, 538645262, 62296931, 197854594, 917988656, 933103628, 494485575, 109484977, 94500428, 658421767, 572614577, 190574812, 26298066, 367341755, 288996710, 186625781, 314638908, 417978959, 200112530, 169149366, 410633240, 617326254, 715955248, 236469098, 119282187, 476641698, 739325094, 819941108, 937069049, 131902396, 669674030, 43770079, 409777481, 119653061, 720236346, 921025391, 322723901, 214032572, 823560303, 73079502, 229613094, 811758163, 985745391, 784898792, 688205407, 40479132, 851018792, 391431839, 491699124, 726660979, 320508852, 712305878, 343346243, 332226862, 840906167, 510495867, 909459108, 45307769, 678216782, 519534807, 829177532, 465943833, 924386057, 139755190, 367576980, 734831153, 137225015, 294470363, 832508500, 416675019, 595173410, 522570770, 862605230, 262458936, 423967835, 805039964, 338395096, 891278643, 131335316, 780009143, 806999628, 163712255, 171132344, 820013723, 930164639, 508248227, 640840162, 367814847, 125058879, 30889300, 481208173, 266163120, 671600571, 489353118, 22481829, 85251400, 806637936, 884380822, 948932241, 958758318, 909817702, 916590208, 326335589, 707624954, 534358154, 780446825, 996228166, 189566054, 763725844, 844165866, 600898977, 318600750, 420982970, 36786202, 627790745, 318219398, 416637676, 481190165, 127939906, 357550789, 689684662, 764562030, 372695868, 791375431, 227118046, 704897510, 60085582, 837247352, 268069908, 144372952, 821756256, 702259101, 988488333, 351158790, 575725192, 493901749, 876339061, 594666169, 687391947, 168303441, 409970589, 886082676, 405851357, 703325166, 696251502, 280475243, 291048434, 2397223, 733654301, 929083923, 687174827, 382760984, 564324792, 966077670, 209077552, 530928532, 65951649, 437260243, 121978160, 556882540, 701920490, 564305537, 786118343, 752675491, 305715439, 499440933, 334437277, 422924730, 120424537, 892330840, 831142589, 241335401, 756962988, 867992453, 928991167, 54242097, 832000151, 814426459, 124857101, 695339788, 829961762, 238688181, 179542009, 987777448, 98504171, 862530512, 796052153, 356136085, 329492358, 553530433, 588265989, 952169751, 826390150, 749973091, 597536429, 890335631, 559407284, 200622911, 705935350, 713100069, 858835216, 32386059, 941201437, 5457201, 252692618, 154010095, 150398729, 532082511, 173972364, 704520636, 273012312, 345803163, 206286265, 415728421, 735338530, 734764134, 968079279, 315662088, 462985445, 432288966, 776685372, 733514509, 546829873, 695622614, 939022161, 453618817, 349950689, 432522889, 390649377, 385048020, 410475231, 80859192, 201171210, 943122306, 199461048, 191426001, 701885190, 228142864, 306626536, 984869914, 793598649, 953533354, 257210055, 486996147, 583987200, 9844700, 291473493, 12348677, 369938144, 993729431, 418227032, 349402448, 445111273, 285525062, 485949796, 171655474, 761367329, 217352666, 638048907, 788788274, 933125220, 175692955, 601357760, 712272393, 187551344, 234659946, 798318163, 853897114, 955917655, 353437095, 968484425, 340447319, 281298024, 400240168, 48914057, 897029357, 866803392, 760603740, 981705205, 183047127, 394927604, 45880290, 584553340, 509478937, 581139620, 63952178, 957261722, 301333359, 964689145, 242821114, 860918503, 541185684, 150829967, 971092942, 673343800, 449549031, 667947981, 264751260, 447003254 }

    Returns: 1023613047

  28. {100 }

    {1, 2 }

    Returns: 101

  29. {10, 8 }

    {1, 5 }

    Returns: 13

  30. {6 }

    {1, 2, 3 }

    Returns: 7

  31. {100, 5, 6 }

    {2, 3 }

    Returns: 102

  32. {3, 3, 3 }

    {1, 2 }

    Returns: 6

  33. {20 }

    {2, 5 }

    Returns: 22

  34. {10 }

    {3, 6 }

    Returns: 13

  35. {3, 3, 2 }

    {6, 7, 8, 9 }

    Returns: 10

  36. {5, 1 }

    {10, 5, 9, 3 }

    Returns: 8

  37. {100 }

    {2, 4, 8 }

    Returns: 102

  38. {10 }

    {5, 6, 7, 8 }

    Returns: 15

  39. {529726454, 635563989, 820658035, 403555511, 824332069, 376364992, 171801805, 121126556, 793491209, 810549861, 429360464, 453749194, 477698730, 711207388, 659877994, 831652008, 407104906, 63094089, 301869428, 391133982, 347667821, 678416488, 521493795, 772712441, 896598741, 997755472, 149994359, 471873772, 126011889, 318821708, 372533347, 42192023, 205601541, 921513995, 856421583, 135718218, 281784347, 753159802, 725334779, 952799260, 164807467, 342999392, 241371955, 802933109, 76742245, 483044784, 496420367, 115619147, 806844955, 260816840, 795490155, 533456228, 454518043, 529457728, 875606385, 571335120, 575305586, 696546927, 666756010, 568807188, 358799336, 269792327, 286718235, 585111487, 9111720, 9657521, 422459460, 735414065, 673439650, 861201540, 100568138, 340399707, 495235011, 36732360, 959270062, 802463183, 988671452, 931425483, 84300467, 432893154, 990742507, 261571117, 415149157, 438471499, 433365093, 862054656, 630040565, 287473404, 622599218, 766613690, 511904511, 775301756, 695946121, 955324088, 884716402, 595377757, 684453954, 613626684, 698111232, 433418502, 815323303, 625084264, 303664825, 39930128, 581503937, 912226465, 856705648, 84964586, 317967469, 535415329, 843402540, 659204181, 806721664, 765643253, 167414779, 142353025, 763706984, 381504131, 458144029, 242326467, 352473399, 611911130, 699471323, 424396366, 449562747, 350417435, 989215902, 636986903, 24020328, 416522962, 672528098, 373852737, 670374793, 987615870, 408634689, 514032639, 203696536, 284161238, 285500304, 407734188, 289632433, 397146913, 378587932, 754910476, 542922717, 821213354, 18555589, 432830776, 772131015, 489607166, 231251287, 120530081, 373858466, 674290045, 925986897, 344059434, 386471231, 766592622, 904256446, 961708498, 40904870, 885804038, 797599969, 810403561, 123411105, 277805120, 705385664, 474935011, 792072538, 323319190, 216253898, 309361028, 453534118, 313445529, 714142735, 851400799, 811718100, 782846748, 439229947, 100590896, 310118491, 51335652, 961685236, 381031898, 726914147, 265527253, 550705381, 744836944, 640382450, 957435553, 226442203, 396186209, 295207536, 839403883, 702354893, 247575728, 493273584, 181286231, 350979839, 840123748, 37744750, 849252593, 918856211, 77496635, 808969470, 678204829, 224744836, 713692132, 501664163, 396577547, 569458043, 526946554, 813476826, 442620306, 885311264, 264772282, 753408314, 365274654, 661086372, 673093694, 181496164, 535821404, 613251184, 885324933, 896029922, 102137402, 454435247, 205137464, 598768336, 323760666, 659011282, 398339280, 672847052, 296406143, 996176878, 189031208, 372272017, 854097115, 17167070, 935951287, 901505814, 709344674, 636707759, 305261743, 955256096, 303891054, 372679212, 808178468, 527341363, 396588886, 886128479, 161082314, 603541062, 737988188, 669206794, 871411884, 643851555, 160991927, 587584669, 146277970, 654556662, 987318217, 526427430, 50668612, 653277219, 207467587, 251676322, 766455272, 212336671, 989137775, 526250963, 102817704, 392623336, 150879677, 66177649, 866914361, 720946121, 170442622, 305277010, 148712860, 211674171, 101772957, 478676022, 308564539, 263835245, 50625253, 308374076, 762345897, 336189509, 307906023, 451100801, 540647241, 344836478, 553590610, 722419629, 483851575, 256219002, 728278800, 333839446, 700793706 }

    {329607089, 4994094, 74841187, 55964717, 813308202, 425898625, 696162175, 742847506, 81406313, 520536643, 308884881, 251191050, 824602514, 158285159, 683087168, 119996403, 871717645, 172891302, 948536825, 699489453, 251370990, 370747607, 405628468, 924658465, 597614773, 274792891, 37117038, 171017318, 763721584, 326170671, 822568845, 757192122, 736695265, 696318325, 712583783, 136966630, 802840590, 51156906, 412023521, 611829866, 365225733, 921386175, 384312287, 574029130, 223469603, 637793217, 643822783, 609538705, 19370978, 540561758, 479199306, 587921471, 657152056, 402527892, 982532915, 343775703, 226629799, 722568566, 93739871, 531363495, 195762724, 16206611, 636568814, 802767500, 721087111, 995150969, 493219000, 30503071, 955281655, 347033363, 204341966, 397855803, 431813345, 217069420, 604538794, 604758109, 881494014, 894082913, 835109582, 37876343, 652526531, 636559557, 946188011, 333346774, 794278993, 537153638, 679038182, 752634173, 767949305, 983254211, 152812685, 91595734, 196219541, 623186048, 311059161, 933318605, 436510137, 288724713, 836890979, 608521312, 869139209, 766409652, 980326161, 709657498, 693880046, 927752012, 878441381, 99163131, 528350182, 192477953, 250194696, 265815536, 191872409, 331701452, 618911445, 646943757, 732176706, 882767718, 220375295, 637809500, 954360798, 698793146, 943435248, 817001737, 980933704, 285850025, 290924321, 572521170, 238042926, 44243961, 823353733, 592611955, 609147621, 352694334, 226059951, 644081879, 77967680, 369648176, 723807503, 63129001, 267163501, 838377010, 378868560, 839670074, 555638884, 111053950, 365552068, 14039555, 978668070, 880603570, 23874873, 992134306, 191469225, 277373283, 417334237, 327825738, 42000420, 663598990, 276390929, 335835886, 367464415, 10333987, 224782450, 137406972, 237489246, 120132626, 185841544, 668156699, 968780594, 833873150, 270046632, 532066457, 799617771, 255673631, 280916000, 85427972, 625951305, 700079856, 628734486, 267087721, 570224032, 369102641, 875796501, 519212399, 790885341, 719984648, 280846785, 75248911, 539013405, 638017000, 185792510, 233534346, 777478032, 306340235, 504366501, 986319934, 793053638, 156525000, 380756271, 141538369, 55070957, 634455228, 314944785, 384688374, 569829452, 373486133, 475140984, 6756399, 874565700, 73970735, 47610370, 126392854, 818026263, 296482944, 332598694, 743799970, 995028036, 933372699, 594137650, 730836001, 79684782, 234015460, 644443549, 522404961, 504621247, 733755794, 200540294, 770861691, 935548131, 522982889, 51953949, 558110851, 18901868, 227750428, 185523294, 833966631, 282248452, 39841515, 800461145, 513996092, 559336555, 196477239, 512648551, 487690717, 596429304, 450175106, 459052234, 549085902, 809894329, 467562936, 26324653, 88755755, 702147237, 754280148, 309651659, 983556462, 175640604, 603050684, 988262360, 971372337, 346995182, 797256206, 63608231, 313909114, 262892307, 466766759, 674165419, 577407933, 480821619, 291272246, 471604362, 777129967, 809264931, 54187025, 806443218, 140766620, 122175203, 964418929, 167174003, 169410371, 510633834, 787411858, 657537877, 927811678, 220130920, 337905092, 879905937, 356279739, 552777944, 306735761, 239747948, 64280025, 370479455, 154071415, 327767511, 63622826, 216139948, 717475410, 511002762, 142158368 }

    Returns: 1011193090

  40. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {1000000000 }

    Returns: 6000000000

  41. {4, 4 }

    {1, 3 }

    Returns: 7

  42. {999990617, 999999114, 999997223, 999993085, 999992207, 999991665, 999994614, 999999508, 999993351, 999998579, 999997638, 999999973, 999991310, 999999941, 999992237, 999996074, 999999460, 999996574, 999990828, 999994264, 999994789, 999994632, 999997433, 999993571, 999994218, 999998470, 999997138, 999994877, 999995933, 999996865, 999996071, 999990198, 999995978, 999996942, 999996931, 999991833, 999998607, 999991544, 999994989, 999991958, 999993771, 999992627, 999995579, 999995081, 999996216, 999991463, 999994802, 999995676, 999991685, 999995630, 999993587, 999996474, 999993909, 999991020, 999990044, 999998127, 999993138, 999990830, 999993004, 999992719, 999997695, 999999075, 999992916, 999993673, 999999664, 999993495, 999999154, 999998271, 999998687, 999994143, 999993876, 999996105, 999990418, 999999455, 999991186, 999996633, 999994566, 999999636, 999995957, 999996250, 999998913, 999993192, 999992724, 999992822, 999994212, 999996416, 999994597, 999997349, 999997246, 999997601, 999990068, 999994940, 999990324, 999996632, 999992261, 999999988, 999993774, 999991414, 999991906, 999992461, 999999205, 999999430, 999998566, 999999622, 999992533, 999993399, 999999903, 999997098, 999996683, 999999508, 999993348, 999999244, 999992699, 999999720, 999995714, 999990559, 999996135, 999990311, 999991556, 999993381, 999991560, 999995271, 999991969, 999991883, 999991903, 999994229, 999995519, 999999325, 999999291, 999991073, 999995433, 999992144, 999990503, 999997647, 999995414, 999993035, 999994694, 999995317, 999993781, 999991376, 999998472, 999997129, 999994268, 999991171, 999990497, 999999981, 999991730, 999996632, 999990292, 999993285, 999993660, 999991851, 999992204, 999999277, 999997382, 999997755, 999997154, 999996549, 999997079, 999996445, 999997621, 999992512, 999992236, 999991772, 999990159, 999997650, 999994807, 999998500, 999992966, 999992236, 999999876, 999995086, 999993013, 999994144, 999996257, 999993509, 999997773, 999991635, 999990141, 999998064, 999998568, 999997449, 999993563, 999990772, 999996725, 999994593, 999998526, 999993879, 999991142, 999995605, 999993971, 999998763, 999991765, 999996207, 999994182, 999995572, 999993857, 999998989, 999994072, 999990471, 999991224, 999997596, 999995557, 999994237, 999995387, 999995462, 999991394, 999993160, 999997096, 999995182, 999994872, 999999312, 999992631, 999992083, 999990083, 999993004, 999996676, 999992257, 999990530, 999997817, 999991510, 999994501, 999990228, 999993275, 999994356, 999994410, 999992495, 999991861, 999997046, 999990214, 999992331, 999991918, 999991458, 999991536, 999999803, 999990493, 999990645, 999991196, 999993652, 999991389, 999996378, 999992172, 999990701, 999992657, 999994254, 999994432, 999995660, 999994578, 999996689, 999996190, 999992395, 999998199, 999994339, 999996270, 999995122, 999998695, 999990680, 999991264, 999990556, 999991374, 999991478, 999996535, 999993292, 999996584, 999991718, 999996742, 999997076, 999992363, 999997938, 999994376, 999997400, 999997964, 999996548, 999998101, 999990621, 999994450, 999992532, 999999929, 999999027, 999992869, 999996119, 999995070, 999991067, 999994106, 999991340, 999999837, 999992801, 999992019, 999991101, 999997004, 999997041, 999996227, 999997187, 999990332, 999992810, 999998905, 999997074, 999993534, 999994916, 999998660 }

    {638422091, 943327685, 953443377, 876855543, 69755937, 237379108, 349517446, 588219757, 856669180, 57418419, 995706888, 823089413, 65103349, 625032173, 387451660, 469262010, 562402337, 298625211, 295166343, 57467588, 799878207, 555319302, 382697714, 476667373, 70575322, 260401256, 296864820, 774044600, 697517722, 1229905, 950955940, 335939812, 797073941, 756915668, 65311706, 719346229, 846811128, 414829151, 307565985, 555996659, 324763921, 155789225, 231602423, 389867270, 780821397, 619054082, 711645631, 195740085, 917679293, 6811973, 253207673, 570073851, 414647626, 635905386, 46741223, 337739300, 896306641, 343606043, 111783899, 446340714, 197352299, 915256191, 782280525, 846942591, 524688210, 700108582, 566288820, 371499337, 114937733, 726371156, 927495995, 292218005, 882160380, 11614770, 682085274, 662981777, 630668851, 246247256, 858721861, 548348143, 105575580, 964445885, 118421994, 520223206, 452867622, 17679568, 857962505, 201690614, 213801962, 822262755, 648031327, 411154260, 737518945, 282828203, 110613203, 114723507, 982936785, 676902022, 486222843, 950390869, 255789529, 266235190, 242608873, 137949909, 277849959, 777210499, 653448037, 908518809, 23457754, 364686249, 309383304, 129033334, 329132134, 280321649, 501772891, 781999755, 150517568, 212251747, 983690369, 364319530, 34514501, 484238047, 775473789, 624549798, 767066250, 886086991, 739273304, 750003034, 415505364, 78012498, 552910254, 671294893, 344247687, 795519126, 661761153, 474613997, 425245976, 315209189, 235649158, 448703730, 679895437, 545032461, 430253415, 861543922, 677870461, 932026305, 496060029, 828388028, 144278051, 332266749, 192707557, 31308903, 816504795, 820697698, 655858700, 583571044, 559301040, 395132003, 186090429, 974806404, 473144501, 739000682, 498617648, 669908539, 387036160, 12895152, 144522536, 812282135, 328104340, 380171693, 113502216, 860516128, 777720505, 543755630, 722060050, 455590965, 328298286, 70636430, 136495344, 472576336, 402903178, 329202901, 503885239, 219407972, 2416950, 12260290, 655495368, 561717989, 407392293, 841585796, 389040744, 733053145, 433102830, 887658391, 402961683, 672655341, 900553542, 400000570, 337453827, 81174233, 780172262, 450956043, 941690361, 410409118, 847228024, 516266762, 866000082, 175526310, 586903191, 2495426, 500618997, 989806368, 184214678, 4504235, 61730691, 186631627, 16764525, 717226058, 748349615, 276673169, 411328206, 137390359, 9726313, 696947387, 877565101, 265204347, 369602727, 630634995, 665204917, 707056553, 564325579, 297893530, 10528947, 358532291, 708302648, 857756971, 874799052, 426819081, 885799632, 314218594, 281830858, 386418628, 156541313, 318561887, 243439215, 70788356, 505193513, 112720091, 788014413, 106059480, 241909611, 51858970, 95966190, 104152275, 748806356, 826047642, 369356621, 970925434, 309198988, 887077889, 530498339, 873524567, 37487771, 541027285, 232056857, 745790418, 251300607, 959372261, 25125850, 137100238, 126107206, 159473060, 376035218, 282648519, 478034946, 471990784, 353436874, 983228459, 584710874, 993967638, 941804290, 826620484, 45826608, 37770479, 930772758, 647149315, 716334472, 152645730, 470591101, 25533460, 39723619, 1089439, 899058026, 77211389, 394633075, 983631234, 675518158, 645933682, 943003494, 553160359 }

    Returns: 1713220394

  43. {100, 100 }

    {1, 150 }

    Returns: 201

  44. {334104409, 676489600, 731822587, 198730287, 182126102, 714995313, 790607298, 468890240, 231274877, 758923748, 183435189, 86954286, 335090553, 917666480, 529751709, 815058400, 837352543, 625521796, 669784993, 853947167, 674112962, 749143070, 859353238, 883627957, 66480347, 327042838, 334273606, 249241506, 857462810, 615740802, 69413114, 705749216, 606803322, 400935124, 515998785, 668678747, 122650052, 840116414, 566173792, 795036880, 646158268, 906196963, 95770880, 742082386, 315060617, 365972468, 394292755, 729945350, 594831556, 623761251 }

    {235957311, 50865007, 173082491, 999333268, 1639024, 558353828, 804859234, 666400296, 577131936, 903470965, 365531674, 951614295, 673531580, 847612108, 448239624, 691943100, 543096970, 865844327, 974039869, 312566995, 155964177, 953794609, 436456882, 718834968, 664555644, 144890417, 113148383, 212546470, 108230719, 98236863, 58652474, 431456048, 874941431, 784716110, 179644007, 841496435, 508990263, 60682266, 889728661, 283648699, 833295752, 806306035, 265085036, 259779148, 468336891, 276178733, 566370817, 370617493, 426897798, 890950568 }

    Returns: 1082460059

  45. {9, 10 }

    {3, 8 }

    Returns: 17

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: