Untitled

Sở giao dịch chứng khoán
John cần kiếm tiền, vì vậy anh quyết định mua cổ phiếu của một công ty. Mỗi ngày, John có thể mua cổ phiếu của công ty, bán một số hoặc tất cả cổ phiếu mà bạn đã mua hoặc không làm gì cả.

Tuy nhiên, mỗi ngày anh ta có thể mua tối đa một cổ phiếu từ công ty này. Rất may mắn, anh ta có thông tin chính xác về giá cổ phiếu trong N ngày tới từ người bạn của mình.

Nhưng anh ta không biết làm thế nào để kiếm được tiền tối đa từ thông tin này.

Cung cấp thông tin về giá cổ phiếu trong N ngày tới, xin vui lòng giúp anh ta kiếm được tiền tối đa.

[Hạn chế]

Trong trường hợp thử nghiệm, có 40% với 3 < = N < = 10, 40% với 10 < N < = 20 và 20% với 20 < N < = 30.

Giới hạn thời gian: 5 giây (Java: 10 giây).

Hạn mức gửi: 10 lần.

[Ví dụ]

Nếu anh ta có thông tin về giá trong 4 ngày tới là 8, 5, 1, 10, thì anh ta có thể mua cổ phiếu trong 3 ngày đầu tiên với tổng giá là 14, và anh ta bán chúng vào ngày cuối cùng để có được 30

Vì vậy, tổng số tiền anh ta có thể kiếm được là 30-14 = 16.

[Đầu vào]

Có thể có nhiều hơn một trường hợp kiểm thử trong tệp đầu vào. Dòng đầu tiên có T, số lượng trường hợp kiểm thử.

Sau đó, các trường hợp kiểm thử hoàn toàn T được cung cấp trong các dòng sau (1 < = T < = 50) Trong mỗi trường hợp kiểm thử, dòng đầu tiên có số nguyên N (3 < = N < = 30) là số ngày, trong dòng tiếp theo là giá cổ phiếu cho N ngày tiếp theo K (1 < = K < = 10000).

[Đầu ra]
Trong mỗi dòng, bắt đầu bằng "#x", trong đó x là số trường hợp thử nghiệm, theo sau là khoảng trắng và số tiền tối đa mà John có thể kiếm được.

[Mẫu]

Đầu vào
5

4

8 5 1 10

7

9 9 3 5 6 6 2

10

2 2 6 3 8 7 2 5 3 4

5

9 7 6 3 1

10

7 2 9 10 3 8 10 6 5 4

Ra

#1 16

#2 4

#3 23

#4 0

#5 21




50
4
6450 6630 7580 380 
6
7240 7420 5300 7790 3170 360 
9
9215 1445 255 70 55 20 5 5 5 
7
3650 1405 885 695 525 170 65 
4
6240 850 9550 7570 
7
4835 3040 2780 885 650 350 285 
9
5380 5390 1190 830 9300 5420 8340 1160 6400 
9
7050 9310 9780 3070 6740 3870 220 7460 9250 
5
2710 8300 7780 5740 980 
3
9870 2910 1620 
4
3560 7680 6560 5750 
4
530 3510 1510 9420 
4
9670 4310 1080 1920 
6
3380 4580 2880 7540 3840 9460 
4
2100 7590 2220 5890 
6
9470 5070 310 4140 1690 9010 
6
7630 6560 4110 3600 6250 5380 
9
4840 5960 420 6030 3510 2920 8370 3750 210 
6
220 3490 2000 6690 4850 2820 
7
540 10000 4190 9390 9010 7890 1280 
12
7290 8940 6490 4840 8080 4220 3110 6180 8140 5150 3100 6170 
15
4520 6010 2500 5200 5570 7990 3040 2250 90 8450 6100 9900 7030 1960 4860 
13
3440 5240 5880 3150 5040 4490 2010 4590 6190 5810 7970 7990 2820 
14
7990 100 1580 4730 6230 5390 2930 390 1800 1910 6580 9590 1920 8160 
13
1570 5120 2030 6350 2730 560 3290 6470 3630 8870 8760 4340 8700 
13
8450 4170 8820 9990 3230 6520 220 7000 5580 4770 8930 3900 760 
12
6010 5110 40 8700 8620 6890 4020 7900 2560 4240 30 5860 
17
2860 890 4270 6180 7580 8330 9330 1700 1550 7220 1900 9770 3300 3690 6930 4260 5560 
19
5500 4420 5130 1460 610 7190 7540 1400 4240 2800 9970 6880 5300 5500 4380 8670 9500 1940 1960 
16
4170 2870 1060 4890 2830 4560 7350 1150 7020 3170 6720 7870 2640 3140 3560 1860 
18
9130 8090 8330 9460 3140 7570 3220 5590 6470 9830 4820 1450 1970 2230 1300 1620 5360 4510 
17
4670 450 6600 2930 4400 2540 250 1550 5110 7460 6500 1870 3140 4750 230 1690 190 
12
9060 9590 3920 2030 6260 4780 4150 3150 8250 3350 8750 3730 
19
8340 710 4880 2980 5190 1780 7740 2710 7640 6690 1930 9860 1030 4810 2140 6280 8030 1000 5280 
20
5440 9250 240 9730 620 1820 40 4330 5060 5940 7260 320 4930 1430 2230 2870 650 9010 1880 3610 
13
9750 2710 1710 2360 8340 7120 7610 8970 6680 2860 5510 1410 6950 
18
6250 200 1260 5770 6950 6590 3030 3720 4670 6790 5940 8520 4850 190 4650 1200 1530 8010 
20
610 9270 110 7580 1710 3160 5770 2280 440 7590 1650 1100 8830 870 5660 4880 5780 4750 6260 6280 
16
9290 4240 5210 9030 9630 1240 5970 7380 2620 1960 5260 2650 2610 2030 1170 310 
15
120 7720 4120 5480 1540 5210 7910 9250 1890 7640 9410 8520 6630 8300 9010 
24
9590 5790 3660 80 4780 2010 590 4400 3040 7610 3580 3250 4780 1090 1140 8880 8020 8510 4610 4290 9940 3850 4060 5410 
22
7050 8360 3570 730 3510 8240 4860 5570 2170 6270 3580 5270 3580 3380 2720 8700 3620 8970 230 6180 1130 7180 
23
5860 420 4240 1300 2300 5660 5600 9330 2970 8560 540 9630 5850 7350 6550 9730 4580 3700 5330 9640 6080 4840 9120 
24
680 8490 6760 9390 2240 1430 7550 5120 7420 1760 4600 8260 2220 8710 6270 9350 2060 7840 8510 3990 2800 7020 1940 7350 
24
5350 5570 9940 1770 7060 9630 5490 8820 3010 4140 6420 8560 8560 1430 4630 6120 8780 4250 6790 7530 4440 2970 6740 410 
25
8760 730 8190 6110 180 9330 1130 6960 1700 8320 410 4890 6860 910 4980 5900 9910 1460 3540 3150 6520 7410 450 2590 3360 
22
1930 6060 2650 1820 5040 8300 7760 6090 2930 9980 5500 5570 5620 6280 4680 5420 1300 2410 8140 1750 6020 780 
22
6840 2140 9930 8250 6020 3930 7600 6710 4290 280 850 760 7870 4990 9710 2880 8480 6050 5040 2220 6640 7070 
24
110 1720 4900 2410 1650 5430 6200 9140 5920 7050 8190 2330 7510 2060 9760 5400 3040 4230 990 2480 5850 6490 9720 8650 
29
760 5460 7130 5470 6790 7700 2630 5200 9860 2900 9450 8660 5410 2460 5090 3190 8710 6020 3240 1330 4730 1530 880 5710 7640 9020 1040 4240 5280