Problem Statement
You are driving a car along a long straight road. Initially your car has the speed of 0 meters/second. You are going to drive for S seconds. We will number these seconds from 1 to S, inclusive.
You are given N pairs of integers (moments[i], speed_changes[i]). Each such pair has the following meaning: Immediately before second number moments[i] you will instantly increase the speed of your car by speed_changes[i] meters/second.
Compute and return the total distance the car will travel during those S seconds.
Definition
- Class:
- DriveTheCarEasy
- Method:
- calculateDistance
- Parameters:
- int, int, int[], int[]
- Returns:
- long
- Method signature:
- long calculateDistance(int S, int N, int[] speed_changes, int[] moments)
- (be sure your method is public)
Constraints
- S will be between 1 and 109, inclusive.
- N will be between 1 and 100, inclusive.
- speed_changes and moments will have exactly N elements each.
- Each element of speed_changes will be between 1 and 1000, inclusive.
- Each element of moments will be between 1 and S, inclusive.
Examples
1000
1
{1000}
{1}
Returns: 1000000
At the beginning (before second number 1) you increase the speed of your car from 0 m/s to 1000 m/s. The car then moves at this speed for 1000 seconds, so it will travel 1,000,000 meters.
5
5
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
Returns: 35
The speed during each second will be 1, 3, 6, 10 and 15 m/s respectively, so the answer is 1+3+6+10+15 = 35 meters.
100
5
{1, 2, 3, 4, 5}
{100, 100, 100, 100, 100}
Returns: 15
Note that moments may contain the same value multiple times. If it does, each occurrence should be processed separately. In this example your car stands still for 99 seconds. Then, immediately before the second #100, five separate speedups occur. In total, you increase the speed of your car by 1+2+3+4+5 = 15 m/s. Thus, during second #100 the car will travel 15 meters.
1000000000
3
{1000, 1000, 1000}
{3, 2, 1}
Returns: 2999999997000
Note that the elements of moments do not have to be sorted. Watch out for integer overflow.
100
10
{522,426,772,447,497,775,982,417,932,728}
{75,45,81,29,2,25,84,56,2,37}
Returns: 367474
1000000000
100
{857,918,679,340,868,940,593,991,355,431,757,934,676,221, 922,511,467,691,835,965,221,501,325,302,896,489,607,432, 968,475,84,694,354,409,643,951,420,607,167,438,986,483, 806,858,553,554,325,279,327,832,200,658,992,467,958,600, 473,775,770,718,807,898,530,569,384,913,315,334,392,8, 962,850,61,588,980,890,747,740,469,516,7,299,163,571,455, 590,427,342,239,875,258,377,428,455,653,768,307,878,368,882}
{189330739,802329211,303238506,492686568,125660016,839296263, 492601449,191890310,782177068,818008580,160449218,840594328, 797829355,501899080,545531545,350034067,470338674,533206504, 31262034,677959980,846045895,346948152,506147731,816248153, 37119022,215208399,189766466,137831502,47628333,409233792, 888987010,87027328,421624712,871216480,509928121,14723492, 569328197,807497925,537560717,889089200,846216104,76823620, 242790881,792345559,632488502,70422962,26697435,992120464, 499482549,736386595,940778720,306890639,1849130,672298989, 331602581,206347466,149811929,316412581,927999455,441504628, 673419335,198091552,599715811,441414148,80656954,110880114, 233703686,209550382,214278326,936333553,989214957,989248231, 954621185,909664305,887357564,988670052,922390943,901347593, 528977370,817020443,81469525,101430412,801006699,99958976, 458482217,770179343,91883220,87104584,8454496,269122601, 483571449,667480040,926138238,897273517,774034433,359911957, 94576456,741452977,171601999,723473541}
Returns: 29493629905568
1
1
{826}
{1}
Returns: 826
1
100
{269,98,763,413,523,206,904,410,611,410,262,949,546,987,306,291,542,94,89,729,964,823,297,917,176,965,541,3,256,611,931,609,304,199,825,939,374,846,154,814,886,100,709,479,14,744,94,20,963,829,930,665,385,353,110,356,694,297,831,720,695,154,306,524,231,353,692,413,438,858,266,95,807,868,809,7,992,650,399,698,381,282,119,926,788,944,888,655,489,131,445,434,850,542,741,101,532,568,276,772}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 52248
5
100
{259,836,54,325,949,56,378,83,790,945,268,501,772,675,665,920,516,149,807,591,82,898,841,593,3,768,965,83,366,732,488,64,773,122,632,455,880,889,320,733,90,212,135,37,144,778,345,398,328,566,371,805,279,309,329,429,241,870,314,901,748,965,122,234,997,838,6,711,136,343,420,843,314,901,535,275,177,261,93,562,698,836,420,743,897,110,487,246,524,258,389,789,688,899,913,920,65,727,706,500}
{4,1,3,5,5,5,1,4,4,5,2,5,5,2,1,1,2,3,5,4,3,4,4,2,4,1,1,3,4,1,3,1,5,4,5,3,1,4,4,5,5,2,1,3,3,1,2,3,3,1,1,4,5,1,5,1,1,4,3,2,4,2,3,1,3,2,3,2,2,1,3,4,3,2,2,1,4,2,2,2,1,4,1,3,2,5,4,4,3,1,1,4,2,5,4,4,2,1,3,1}
Returns: 157937
5
100
{68,266,52,319,456,115,380,757,679,526,967,475,249,199,954,991,505,268,66,428,932,786,868,418,768,710,965,475,802,516,2,222,326,419,721,615,674,246,149,788,378,211,485,577,228,135,685,195,581,903,801,359,193,119,528,747,294,798,654,20,688,735,464,685,781,216,131,437,337,454,580,256,322,413,16,788,149,828,741,164,966,270,542,368,235,274,361,106,952,35,460,49,995,974,226,809,25,610,298,567}
{2,5,5,1,1,4,2,4,1,5,4,1,1,2,5,4,2,4,1,2,2,1,4,2,3,5,4,5,3,1,4,3,1,5,5,5,3,1,2,1,3,4,5,3,2,1,1,3,1,1,3,1,2,2,5,3,5,4,4,4,3,2,2,5,1,5,3,3,1,3,3,4,3,1,1,1,4,4,2,3,4,1,4,5,1,5,3,2,2,2,4,4,2,1,4,3,2,5,5,3}
Returns: 145314
5
100
{790,995,16,633,312,853,881,427,355,70,178,739,533,299,720,861,922,601,144,966,104,149,327,555,859,139,970,834,274,145,214,743,879,940,553,495,994,865,886,504,493,221,60,982,64,365,894,175,310,429,995,126,364,715,335,362,345,45,654,520,807,613,263,291,774,643,342,130,953,803,40,338,773,889,931,919,656,547,434,318,391,823,963,972,854,31,851,263,499,819,672,795,554,215,925,141,969,15,993,835}
{3,3,5,5,2,2,5,5,5,5,3,4,3,3,2,1,1,2,2,1,4,1,5,3,3,1,5,1,1,2,5,4,2,2,1,2,1,5,3,2,4,2,3,1,1,1,3,1,4,4,1,3,2,5,5,4,2,2,1,1,3,2,1,5,2,1,4,4,2,1,3,1,1,3,3,2,4,1,1,5,3,3,1,1,1,4,3,2,3,1,1,4,2,4,4,3,4,1,5,3}
Returns: 189333
5
100
{781,865,504,881,490,82,943,164,933,95,978,714,797,565,936,359,581,144,589,232,322,719,646,19,770,397,617,611,274,64,873,640,302,789,980,388,531,864,952,550,184,56,352,443,112,448,443,822,960,926,884,614,982,447,834,215,743,856,353,343,967,374,862,18,268,557,645,173,210,923,637,430,423,574,387,673,920,569,386,979,649,841,800,457,751,933,138,65,785,360,694,672,545,121,879,377,599,635,348,707}
{1,5,5,3,4,5,2,1,2,2,3,2,1,1,1,1,2,4,4,4,3,1,2,2,1,2,3,5,3,3,2,3,1,1,2,3,4,5,5,5,5,4,5,4,3,3,3,3,5,4,5,5,4,1,1,1,5,2,3,2,2,4,2,4,3,2,4,5,2,5,2,3,4,1,5,1,2,5,2,4,5,5,4,4,3,3,4,1,4,1,5,5,2,4,4,3,3,2,4,4}
Returns: 163453
5
100
{526,396,600,562,755,736,938,228,149,118,822,677,486,785,577,114,286,680,352,656,247,742,728,589,697,104,998,597,535,725,807,686,151,785,600,548,917,224,351,620,166,376,199,235,281,958,95,623,849,655,986,828,731,496,719,224,757,549,250,998,620,461,144,702,436,179,13,138,259,85,136,161,589,800,438,23,664,224,10,89,921,892,666,645,996,647,747,543,759,271,331,301,126,313,277,2,15,218,599,717}
{1,2,4,4,3,4,4,4,5,4,2,5,2,4,3,1,2,2,4,3,4,2,2,5,1,3,5,4,3,5,1,3,5,3,3,1,5,2,2,5,1,1,2,3,5,1,4,4,2,1,1,4,1,4,5,2,1,2,4,5,4,2,3,2,1,3,1,5,5,2,3,3,2,3,2,4,4,2,2,1,4,5,4,2,2,2,4,3,1,1,3,4,3,1,2,1,1,1,4,3}
Returns: 149940
1000000000
100
{902,158,615,659,873,612,681,623,253,359,978,897,614,613,494,371,882,763,612,364,397,582,200,784,357,995,823,732,151,950,174,46,375,693,83,938,778,141,649,661,78,331,294,117,456,36,464,78,477,460,458,293,889,554,523,544,273,97,231,323,587,519,922,147,796,953,571,246,616,500,790,408,885,748,8,526,15,575,70,174,4,155,629,204,761,707,363,69,866,164,251,919,829,61,835,630,734,810,689,143}
{5,4,3,1,4,2,1,5,4,1,4,3,3,1,2,2,4,1,5,1,1,3,4,4,1,5,5,5,1,1,5,2,3,1,4,3,3,4,1,5,2,5,4,1,1,4,3,3,1,4,3,5,2,1,2,5,2,2,3,3,5,2,4,4,5,2,3,1,1,3,3,4,5,2,4,2,4,4,2,4,3,5,1,4,4,1,4,3,5,3,3,3,2,2,4,5,5,2,1,2}
Returns: 49686999898682
1000000000
100
{483,31,984,7,473,402,743,700,436,360,442,491,721,494,462,943,734,656,967,63,1000,525,828,71,780,960,769,85,742,191,828,53,283,583,32,940,65,261,243,856,589,350,810,717,859,462,315,64,65,931,9,430,507,498,275,653,199,888,604,521,650,434,651,552,328,237,388,782,847,477,892,488,563,112,960,979,698,571,621,429,456,11,280,146,211,197,542,664,784,981,940,923,795,346,232,664,538,111,357,508}
{4,3,3,1,1,2,4,4,3,4,3,3,1,5,1,2,2,5,5,4,1,4,2,1,4,5,3,2,1,2,5,2,2,5,3,5,4,2,4,5,1,3,1,2,5,2,5,4,5,5,5,5,4,3,3,5,4,2,4,5,5,1,2,2,5,3,2,4,5,1,4,5,1,2,3,4,2,2,2,1,2,1,2,1,2,2,3,4,3,2,3,5,1,4,3,4,1,2,4,5}
Returns: 51777999887014
1000000000
100
{841,226,690,397,774,688,2,575,910,301,996,608,541,920,124,892,96,828,671,456,518,207,369,713,1,686,41,365,361,974,403,960,777,76,93,367,974,340,10,584,847,605,248,295,22,314,996,314,482,41,20,332,312,599,747,453,733,472,656,743,973,939,975,289,429,731,12,479,372,902,702,750,428,889,657,516,941,225,18,117,674,482,22,750,104,939,250,613,445,127,204,350,798,100,79,382,167,15,521,443}
{5,1,1,3,3,3,5,1,2,5,5,3,3,1,3,2,1,2,2,2,4,3,1,3,3,1,1,3,1,5,4,3,1,3,2,1,2,4,4,4,4,3,1,1,1,2,3,5,5,3,2,5,4,5,2,1,5,5,5,1,1,4,2,3,1,3,1,5,5,1,2,5,3,2,5,2,5,4,1,5,4,3,2,5,3,1,5,4,3,1,3,4,1,3,4,4,4,3,3,3}
Returns: 48394999905874
1000000000
100
{622,573,912,9,511,362,519,749,240,444,85,453,998,753,822,637,877,484,526,226,866,323,212,546,508,26,636,721,966,184,667,276,253,936,78,913,447,888,338,292,409,69,141,482,615,692,514,897,630,602,159,677,917,963,986,899,543,758,542,641,817,62,762,459,881,449,922,110,532,988,563,247,390,963,521,36,13,789,971,322,173,205,829,300,812,529,141,169,311,638,134,813,594,113,854,486,490,78,570,776}
{5,5,1,4,5,5,1,3,1,3,1,4,3,1,5,1,2,1,4,2,5,4,1,3,3,5,3,1,1,4,1,5,5,1,5,2,1,2,1,5,3,4,3,3,5,4,4,4,2,3,2,5,4,1,5,4,3,2,1,4,3,1,4,5,5,5,5,4,4,3,2,1,4,5,1,2,1,5,2,1,3,5,4,5,4,5,3,5,1,3,1,4,2,2,5,4,1,1,3,1}
Returns: 52825999888012
1000000000
100
{638,436,520,656,448,694,539,547,120,994,242,103,833,141,160,633,496,732,996,172,411,515,434,943,439,881,247,710,760,281,936,903,740,657,50,949,224,38,930,744,648,29,733,354,321,370,1000,578,626,507,401,236,901,550,539,918,394,574,69,563,908,752,202,835,432,3,865,152,628,483,910,289,445,12,557,570,263,52,469,528,264,712,626,561,180,925,113,393,161,488,472,126,612,901,410,547,377,858,525,880}
{3,2,1,2,1,4,4,4,4,5,4,4,1,1,5,2,4,4,2,3,3,3,4,5,2,5,1,4,2,4,1,2,2,3,2,3,2,5,2,4,5,4,3,4,5,1,3,2,1,2,5,3,1,3,5,5,5,2,5,1,4,5,5,3,3,1,2,2,2,5,5,3,4,3,2,5,2,2,1,3,5,5,5,1,1,1,4,5,1,3,3,1,3,3,1,4,1,5,4,1}
Returns: 51688999894204
1000000000
100
{254,61,830,159,543,536,411,807,354,475,903,980,155,170,601,755,920,553,933,386,702,831,255,765,113,167,102,385,183,967,870,660,964,723,60,546,158,186,533,640,673,591,166,444,764,337,877,26,641,691,293,24,919,811,908,641,579,317,200,564,674,600,884,22,144,679,207,18,898,696,645,479,462,88,130,58,305,932,773,134,159,833,482,826,310,916,926,619,714,617,654,548,529,926,399,764,880,88,127,375}
{705032706,705032708,705032705,705032709,705032709,705032708,705032706,705032705,705032707,705032704,705032709,705032705,705032708,705032709,705032709,705032707,705032708,705032704,705032704,705032709,705032706,705032707,705032705,705032707,705032709,705032706,705032705,705032707,705032709,705032708,705032704,705032704,705032704,705032709,705032707,705032707,705032704,705032704,705032704,705032704,705032706,705032708,705032707,705032704,705032707,705032705,705032704,705032705,705032707,705032706,705032704,705032704,705032704,705032705,705032706,705032705,705032707,705032706,705032709,705032705,705032706,705032708,705032704,705032704,705032708,705032709,705032705,705032708,705032705,705032708,705032709,705032706,705032705,705032706,705032705,705032704,705032709,705032709,705032706,705032709,705032707,705032704,705032708,705032709,705032708,705032709,705032709,705032709,705032704,705032704,705032708,705032707,705032709,705032708,705032708,705032706,705032704,705032708,705032709,705032708}
Returns: 15215002988560
1000000000
100
{771,564,713,707,440,87,203,372,691,845,275,743,962,460,732,194,954,9,205,65,175,257,722,913,846,481,384,464,357,358,827,586,809,860,34,964,287,426,761,891,874,563,365,781,858,397,188,991,690,852,369,364,272,495,570,723,904,985,957,384,304,105,869,785,740,666,873,146,490,770,196,872,31,845,85,584,319,354,56,72,904,964,258,124,598,2,816,546,527,343,415,222,975,793,708,93,940,428,204,956}
{705032709,705032709,705032708,705032704,705032709,705032706,705032708,705032709,705032704,705032705,705032707,705032706,705032708,705032707,705032707,705032705,705032708,705032708,705032705,705032705,705032704,705032705,705032706,705032705,705032709,705032704,705032708,705032705,705032705,705032708,705032704,705032704,705032706,705032704,705032707,705032708,705032707,705032705,705032709,705032706,705032709,705032706,705032709,705032705,705032704,705032706,705032706,705032705,705032706,705032708,705032708,705032706,705032707,705032709,705032709,705032707,705032706,705032709,705032704,705032705,705032708,705032705,705032708,705032706,705032708,705032709,705032709,705032708,705032709,705032709,705032704,705032705,705032706,705032706,705032708,705032708,705032705,705032705,705032709,705032707,705032704,705032709,705032709,705032708,705032707,705032705,705032709,705032705,705032709,705032706,705032708,705032704,705032709,705032707,705032709,705032709,705032709,705032708,705032708,705032704}
Returns: 15914665390233
1000000000
100
{139,495,708,409,296,653,482,608,577,932,393,831,154,105,136,194,225,713,922,438,435,577,734,160,796,813,272,326,921,36,316,76,921,177,313,376,646,258,803,421,48,340,607,226,746,699,459,972,9,462,74,119,523,912,458,424,997,527,272,188,355,960,346,993,947,472,571,739,434,164,434,207,324,472,795,251,878,842,258,499,814,511,758,213,273,20,331,52,916,630,446,495,946,18,116,899,267,772,90,515}
{705032705,705032709,705032708,705032707,705032704,705032709,705032704,705032706,705032704,705032704,705032705,705032708,705032706,705032707,705032706,705032709,705032708,705032707,705032704,705032708,705032704,705032707,705032704,705032704,705032707,705032704,705032709,705032707,705032707,705032705,705032709,705032705,705032709,705032709,705032706,705032704,705032709,705032705,705032709,705032708,705032709,705032709,705032709,705032708,705032706,705032704,705032708,705032709,705032704,705032704,705032705,705032707,705032704,705032709,705032708,705032704,705032707,705032708,705032706,705032705,705032706,705032705,705032708,705032708,705032705,705032704,705032708,705032706,705032707,705032707,705032707,705032704,705032705,705032704,705032705,705032708,705032707,705032708,705032709,705032706,705032708,705032708,705032704,705032706,705032704,705032705,705032706,705032706,705032705,705032707,705032707,705032709,705032704,705032709,705032704,705032709,705032709,705032708,705032708,705032705}
Returns: 14120674319263
1000000000
100
{562,970,46,502,797,249,923,865,528,830,15,703,585,734,808,487,60,462,513,358,143,810,809,887,799,440,548,393,848,981,686,353,647,454,886,490,851,16,352,115,694,503,225,865,832,122,646,567,820,668,356,948,951,235,329,717,552,44,176,333,529,155,607,475,466,991,596,395,197,363,746,411,938,837,984,863,732,810,786,828,49,935,852,464,413,961,565,7,694,140,921,398,864,854,301,651,137,660,718,233}
{705032705,705032707,705032708,705032709,705032704,705032707,705032706,705032708,705032706,705032705,705032706,705032706,705032706,705032704,705032706,705032707,705032708,705032709,705032704,705032707,705032706,705032705,705032708,705032704,705032709,705032707,705032709,705032706,705032704,705032707,705032708,705032705,705032709,705032704,705032706,705032704,705032704,705032708,705032707,705032709,705032709,705032709,705032707,705032709,705032705,705032708,705032707,705032704,705032705,705032708,705032704,705032705,705032709,705032706,705032706,705032706,705032709,705032705,705032709,705032705,705032707,705032706,705032705,705032706,705032704,705032708,705032709,705032707,705032705,705032705,705032708,705032706,705032704,705032705,705032705,705032705,705032707,705032707,705032705,705032707,705032704,705032707,705032706,705032708,705032704,705032704,705032707,705032709,705032704,705032707,705032707,705032704,705032706,705032705,705032706,705032704,705032706,705032705,705032705,705032709}
Returns: 16699278429206
1000000000
100
{957,115,962,264,187,200,980,562,141,272,730,326,306,287,330,656,303,819,663,382,529,257,248,516,636,830,32,247,741,767,606,76,778,433,902,985,160,184,213,723,755,266,192,93,985,540,20,198,687,395,774,58,345,852,827,63,740,859,648,768,711,719,939,773,564,579,671,496,731,813,267,328,127,570,218,129,557,767,659,912,779,736,250,699,382,915,611,998,306,222,893,871,605,884,620,586,851,362,725,844}
{705032704,705032704,705032707,705032707,705032705,705032709,705032709,705032706,705032706,705032708,705032706,705032708,705032707,705032708,705032704,705032708,705032704,705032707,705032707,705032704,705032708,705032708,705032705,705032705,705032709,705032707,705032709,705032707,705032707,705032707,705032707,705032707,705032709,705032709,705032708,705032709,705032708,705032704,705032707,705032708,705032708,705032705,705032706,705032707,705032705,705032707,705032708,705032708,705032709,705032705,705032708,705032705,705032709,705032709,705032706,705032705,705032706,705032704,705032704,705032707,705032708,705032708,705032707,705032705,705032707,705032706,705032708,705032704,705032705,705032706,705032706,705032706,705032705,705032709,705032709,705032708,705032706,705032706,705032704,705032708,705032708,705032706,705032704,705032709,705032709,705032704,705032706,705032707,705032709,705032705,705032709,705032704,705032707,705032705,705032708,705032706,705032708,705032705,705032704,705032705}
Returns: 15939737616063
1000000000
100
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 100000000000000
1000
10
{290,327,477,274,743,886,266,66,886,950}
{975,368,567,733,10,433,804,784,908,375}
Returns: 2478364
1000000000
10
{895,952,893,770,450,153,144,544,57,243}
{31451401,93232116,232810090,94516625,457115437,536346197,622249833,500320066,715292075,786363152}
Returns: 3822017914296
1000
10
{701,149,703,162,224,341,803,172,943,271}
{173,625,82,275,396,833,191,962,3,113}
Returns: 3431829
1000000000
10
{873,188,623,726,581,801,4,848,638,920}
{763731869,325163219,603587710,205402828,326886427,785084586,320156563,541796088,441984380,432494325}
Returns: 2989595513146
1000
10
{780,66,280,556,107,817,976,829,759,129}
{559,683,519,40,110,256,425,657,879,845}
Returns: 2699100
1000000000
10
{811,5,564,473,62,987,288,276,967,987}
{919422925,991295100,801361437,349958951,330482642,868867782,402584853,173612395,22592644,207627485}
Returns: 2783193805689
1000
10
{816,1000,865,154,432,162,666,670,566,839}
{173,822,560,701,578,893,715,708,193,413}
Returns: 2819991
1000000000
10
{672,923,454,587,710,710,126,301,267,757}
{285752826,441179230,776526023,617995571,676872435,418060377,368809904,489927532,782684066,77853369}
Returns: 2953207285015
1000
10
{787,208,563,404,697,42,42,808,414,256}
{130,437,700,836,793,402,934,926,307,850}
Returns: 1598432
1000000000
10
{879,743,910,926,118,885,431,555,180,999}
{921231814,507397421,360858429,799002817,49440607,876884565,306095716,71771915,604953336,658003899}
Returns: 2651108185732
230346597
96
{98,182,731,982,609,713,173,119,405,491,170,436,275,319,439,843,368,779,714,664,600,349,336,265,362,240,396,586,585,595,77,937,203,714,247,171,661,569,112,340,483,399,884,114,612,120,32,265,619,537,538,175,646,879,950,609,818,912,65,987,740,87,632,579,640,130,513,373,301,607,665,199,894,249,563,253,889,55,230,77,875,356,854,84,265,847,497,686,431,900,467,697,276,688,105,105}
{109999458,55524029,146286181,144448463,74685348,32538390,25486850,57418208,127628996,135512654,210034260,38744733,38329793,146116313,72844761,104289737,110834311,155532769,206417399,219357314,210405195,227930293,171298870,182688388,73477184,183756667,229592482,33985280,7053608,46365202,68711986,48370746,220107915,88878595,147239638,134996104,215899965,50992783,126568467,201873148,8895793,230067588,39914169,63726597,134118193,49264147,210178739,17646402,121545499,125119329,177548993,11049078,143335883,120655306,62735800,156595655,98166361,471306,198193214,180542659,189023086,186292680,208051797,209371694,109795843,29671098,59802367,21591950,175331252,151917334,191368367,212686978,220027498,8770304,151656995,124998611,128153574,21752585,156976940,34486746,47974293,100542657,56441960,104854497,119819110,80125355,202393487,166824376,133685657,144760967,171552881,47970612,5070413,78173274,29945689,65619580}
Returns: 5060887199412
467442635
70
{848,712,252,426,225,798,78,6,856,591,85,956,682,721,942,456,604,488,309,201,236,825,840,986,381,129,491,761,214,894,36,251,570,508,576,284,792,353,403,59,932,904,522,907,786,9,91,418,961,766,379,221,29,694,55,321,467,789,571,163,288,112,732,399,530,933,56,411,380,552}
{202577114,444738346,188620510,110858434,246079521,397746775,88366898,308875700,430205634,238450082,219074436,427423906,334933711,123648636,155897942,111870530,199139448,354630138,386069290,257194679,216419102,291426098,431441950,434567425,16355669,131688606,445334058,191910575,270044182,290861726,88636332,348788372,267071300,376868153,26596395,343575505,192752805,421716887,29551986,58420070,193721824,82569311,361187968,187060445,24501131,114602529,416664103,323028411,363141122,34554571,314635459,116334854,138095672,457054272,274966547,101209200,283960896,415120795,97100171,106216215,94937857,404655649,449870254,143682364,435535848,298572433,252105,368679661,88188258,385586413}
Returns: 6859364169823
622908236
69
{549,548,63,316,216,480,469,486,273,243,49,239,191,220,312,531,221,239,598,271,794,928,56,1,49,766,187,62,192,325,285,810,603,330,306,563,689,122,31,638,405,210,10,343,734,647,591,628,639,871,995,761,278,77,164,116,943,200,366,401,497,995,942,54,231,757,338,431,176}
{211296593,541558658,324652907,205247220,276386119,416369209,500351932,263717510,334636407,327840133,537752079,236044966,523905000,462356067,116703600,469187117,524591425,302617658,359955373,141566894,428524929,447479089,262076630,295640604,345543446,214331587,327458765,156512005,52661701,496815587,34747261,464929973,38022416,119132294,418820795,547955342,337388406,613661303,283032463,505657293,603785229,273231897,360511626,159355503,566276246,89258344,81235470,177812104,173738786,342097553,92908288,347267522,92565782,245630229,56252760,619364726,298393231,611284401,268286687,393213776,209937834,97739695,567555839,90033466,196720868,218113303,386491832,121514321,547924017}
Returns: 8676247335684
385354177
22
{990,259,663,982,903,500,585,232,331,145,893,828,974,551,271,271,77,107,499,342,94,545}
{325369732,58496367,344249404,58436793,364247847,96888070,168950974,171016669,339249742,311020591,102720500,324880049,335382860,177223975,21172656,362621589,132813399,357305878,75162310,80640797,43729275,83960922}
Returns: 1906465872424
559554495
75
{350,733,246,944,693,639,976,571,614,130,620,493,15,618,847,738,614,436,764,16,662,637,507,501,822,91,679,420,298,547,238,746,998,624,772,614,241,977,823,715,599,714,179,808,357,793,262,232,408,234,212,993,741,338,179,640,138,815,240,505,162,589,111,35,148,569,814,433,251,424,314,921,542,896,423}
{403285110,217633226,81013692,346348631,424280989,213941191,325908965,275306973,6636601,78648605,409651840,185264981,539407467,332540146,80786485,71082511,527153835,468805835,147444636,446420899,431621873,264645371,60323253,388880044,421394649,462268363,440614392,19932242,467645616,274136563,36388311,486954854,512611112,291688765,400037669,264125321,225062179,197945349,491003507,142115502,141398459,185446333,434406634,548451132,421106882,545088532,306121133,160382889,61617555,117846235,383983047,480698689,289652979,529069237,6456480,328435770,401721482,146986626,439178391,334716850,491808068,506537513,381830207,145854788,333440877,456251184,150336120,490129443,442990717,323375688,367944881,76332897,51709150,101401617,172031523}
Returns: 10166645494492
775918944
24
{320,981,18,395,648,965,809,454,258,972,665,327,923,943,78,868,224,155,374,760,862,502,870,593}
{593776096,209160129,425535386,523937687,199164406,695758451,705124421,18423758,555368493,461297111,166736326,728757968,398597372,66013489,363558320,643294372,653013111,357772263,159292985,765677965,346466963,44432285,25580662,357967666}
Returns: 5489394672150
79181234
45
{324,266,555,577,755,127,237,112,391,123,378,197,525,363,816,827,618,84,276,608,892,689,923,618,951,762,434,461,233,554,693,613,790,55,179,361,283,853,255,333,917,578,383,334,234}
{2264467,50788033,65665802,34653499,69141399,23110822,40041761,29358747,60296001,66659676,77228586,810398,16071845,74398005,11641106,69313909,69503356,11658507,3296309,62895881,69356514,8769441,2879892,56392658,4826706,73739262,55082881,53054110,57431573,3338146,23702765,27533726,43382481,41733775,48673954,49355777,71307268,68167692,42032703,20125156,62317274,3085303,10575280,36236567,16329031}
Returns: 819410064294
858100994
78
{824,689,102,611,286,107,494,482,824,298,512,467,33,913,480,603,71,926,220,545,439,423,280,360,366,407,577,285,345,997,764,702,956,972,527,64,261,411,934,807,153,646,742,265,565,370,549,402,310,364,151,232,489,49,697,287,10,942,977,309,743,552,763,239,837,605,108,313,313,520,586,609,320,392,809,211,791,440}
{418052386,562961373,116366632,178797096,179256174,600579553,461857196,469576075,706837752,382175772,577728561,798972779,633551951,430729257,762348607,313232565,310133058,772217273,732212369,525541718,112677422,306219977,115045493,656065930,420505659,279946994,641921246,839374245,790804715,842847123,331587929,364809662,803069596,536953911,534849182,818235499,208728724,622948711,398335785,540751380,548852566,833156853,524685962,394001240,602408956,31707328,569576467,61020484,392871721,690243235,263604129,828437266,765197573,82360091,206482856,488792704,209468549,144007310,55542625,626161674,644382369,475160502,323034674,70494555,616137584,587768472,801330142,253124454,681403989,651359441,206697349,698716428,647695499,554530274,187814227,579580182,480367089,23877895}
Returns: 14308235292921
876714798
60
{693,514,807,279,676,799,672,728,532,763,306,78,963,851,633,47,165,332,122,127,32,538,370,43,416,28,726,145,723,349,947,781,246,875,526,636,397,923,13,812,758,153,787,329,757,372,639,512,568,567,516,311,963,288,801,874,788,4,506,782}
{69700817,326789353,485809554,660956672,821408089,732967490,8408488,10950953,827822238,305477568,540601684,691260231,290352323,804027738,342107210,786466071,465101770,476054026,872854273,661608783,221021579,364179715,799857548,206400000,183005955,342456610,708118321,232568022,614489784,681432326,43229310,114497154,398278713,394252884,114166720,2301662,639472869,206354835,661503534,323737952,317218450,698587862,553843582,109043860,869184674,784772792,442653227,383648374,397291989,213292788,376875174,850252986,125914892,501322036,156184400,32274274,90493090,261578139,568778831,525181927}
Returns: 15179560959069
526826640
52
{56,587,608,419,809,123,22,323,691,510,77,404,588,913,40,932,602,449,334,704,247,371,963,108,651,765,805,246,754,138,840,90,104,176,217,246,644,365,318,926,729,637,178,632,733,164,173,257,52,225,105,581}
{493741576,251800465,340811277,267321863,484612658,370395909,13691719,399327654,118615452,323826165,164771419,157283042,391746939,237234964,196796894,255510306,451133652,367845225,346858246,466513369,20501292,207708920,24601623,96769181,96220392,323945334,342178327,89209299,434844237,488786504,18889690,359503919,2672000,111401828,283531189,258591063,109630437,395489453,70439998,463826000,408162995,87268378,232905914,452529454,111151278,15069615,62319549,206405911,431290410,287753618,174719356,219814912}
Returns: 5922573519171
100
5
{1, 2, 3, 4, 5 }
{100, 100, 100, 99, 100 }
Returns: 19
1000000000
100
{857, 918, 679, 340, 868, 940, 593, 991, 355, 431, 757, 934, 676, 221, 922, 511, 467, 691, 835, 965, 221, 501, 325, 302, 896, 489, 607, 432, 968, 475, 84, 694, 354, 409, 643, 951, 420, 607, 167, 438, 986, 483, 806, 858, 553, 554, 325, 279, 327, 832, 200, 658, 992, 467, 958, 600, 473, 775, 770, 718, 807, 898, 530, 569, 384, 913, 315, 334, 392, 8, 962, 850, 61, 588, 980, 890, 747, 740, 469, 516, 7, 299, 163, 571, 455, 590, 427, 342, 239, 875, 258, 377, 428, 455, 653, 768, 307, 878, 368, 882 }
{189330739, 802329211, 303238506, 492686568, 125660016, 839296263, 492601449, 191890310, 782177068, 818008580, 160449218, 840594328, 797829355, 501899080, 545531545, 350034067, 470338674, 533206504, 31262034, 677959980, 846045895, 346948152, 506147731, 816248153, 37119022, 215208399, 189766466, 137831502, 47628333, 409233792, 888987010, 87027328, 421624712, 871216480, 509928121, 14723492, 569328197, 807497925, 537560717, 889089200, 846216104, 76823620, 242790881, 792345559, 632488502, 70422962, 26697435, 992120464, 499482549, 736386595, 940778720, 306890639, 1849130, 672298989, 331602581, 206347466, 149811929, 316412581, 927999455, 441504628, 673419335, 198091552, 599715811, 441414148, 80656954, 110880114, 233703686, 209550382, 214278326, 936333553, 989214957, 989248231, 954621185, 909664305, 887357564, 988670052, 922390943, 901347593, 528977370, 817020443, 81469525, 101430412, 801006699, 99958976, 458482217, 770179343, 91883220, 87104584, 8454496, 269122601, 483571449, 667480040, 926138238, 897273517, 774034433, 359911957, 94576456, 741452977, 171601999, 723473541 }
Returns: 29493629905568
2
2
{10, 10 }
{1, 2 }
Returns: 30