It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has *n* cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comfortable to work with and mark the cells with positive numbers from 1 to *n* from the left to the right.

Unfortunately, Joe didn't switch the last security system off. On the plus side, he knows the way it works.

Every minute the security system calculates the total amount of diamonds for each two adjacent cells (for the cells between whose numbers difference equals 1). As a result of this check we get an *n* - 1 sums. If at least one of the sums differs from the corresponding sum received during the previous check, then the security system is triggered.

Joe can move the diamonds from one cell to another between the security system's checks. He manages to move them no more than *m* times between two checks. One of the three following operations is regarded as moving a diamond: moving a diamond from any cell to any other one, moving a diamond from any cell to Joe's pocket, moving a diamond from Joe's pocket to any cell. Initially Joe's pocket is empty, and it can carry an unlimited amount of diamonds. It is considered that before all Joe's actions the system performs at least one check.

In the morning the bank employees will come, which is why Joe has to leave the bank before that moment. Joe has only *k* minutes left before morning, and on each of these *k* minutes he can perform no more than *m* operations. All that remains in Joe's pocket, is considered his loot.

Calculate the largest amount of diamonds Joe can carry with him. Don't forget that the security system shouldn't be triggered (even after Joe leaves the bank) and Joe should leave before morning.
The first line contains integers *n*, *m* and *k* (1 ≤ *n* ≤ 10<sup class="upper-index">4</sup>, 1 ≤ *m*, *k* ≤ 10<sup class="upper-index">9</sup>). The next line contains *n* numbers. The *i*-th number is equal to the amount of diamonds in the *i*-th cell — it is an integer from 0 to 10<sup class="upper-index">5</sup>.
In the second sample Joe can act like this:

The diamonds' initial positions are 4 1 3.

During the first period of time Joe moves a diamond from the 1-th cell to the 2-th one and a diamond from the 3-th cell to his pocket.

By the end of the first period the diamonds' positions are 3 2 2. The check finds no difference and the security system doesn't go off.

During the second period Joe moves a diamond from the 3-rd cell to the 2-nd one and puts a diamond from the 1-st cell to his pocket.

By the end of the second period the diamonds' positions are 2 3 1. The check finds no difference again and the security system doesn't go off.

Now Joe leaves with 2 diamonds in his pocket.
2 3 1
2 3
0
3 2 2
4 1 3
2
5 10 10
7 0 7 0 7
7
6 10 4
1 2 3 4 5 6
0
7 5 2
1 2 3 4 5 6 7
1
16 100 100
30 89 12 84 62 24 10 59 98 21 13 69 65 12 54 32
0
99 999 999
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9
1 1 1
0
0
1 64 25
100000
1600
1 1000000000 1
100
100
1 1 1000000000
100
100
1 1000000000 1000000000
100
100
5 2 9494412
5484 254 1838 18184 9421
0
5 10 7
98765 78654 25669 45126 98745
21
13 94348844 381845400
515 688 5464 155 441 9217 114 21254 55 9449 1800 834 384
55
17 100 100
47 75 22 18 42 53 95 98 94 50 63 55 46 80 9 20 99
9
47 20 1000000
81982 19631 19739 13994 50426 14232 79125 95908 20227 79428 84065 86233 30742 82664 54626 10849 11879 67198 15667 75866 47242 90766 23115 20130 37293 8312 57308 52366 49768 28256 56085 39722 40397 14166 16743 28814 40538 50753 60900 99449 94318 54247 10563 5260 76407 42235 417
0
58 5858758 7544547
6977 5621 6200 6790 7495 5511 6214 6771 6526 6557 5936 7020 6925 5462 7519 6166 5974 6839 6505 7113 5674 6729 6832 6735 5363 5817 6242 7465 7252 6427 7262 5885 6327 7046 6922 5607 7238 5471 7145 5822 5465 6369 6115 5694 6561 7330 7089 7397 7409 7093 7537 7279 7613 6764 7349 7095 6967 5984
0
79 5464 64574
3800 2020 2259 503 4922 975 5869 6140 3808 2635 3420 992 4683 3748 5732 4787 6564 3302 6153 4955 2958 6107 2875 3449 1755 5029 5072 5622 2139 1892 4640 1199 3918 1061 4074 5098 4939 5496 2019 356 5849 4796 4446 4633 1386 1129 3351 639 2040 3769 4106 4048 3959 931 3457 1938 4587 6438 2938 132 2434 3727 3926 2135 1665 2871 2798 6359 989 6220 97 2116 2048 251 4264 3841 4428 5286 1914
97
95 97575868 5
4612 1644 3613 5413 5649 2419 5416 3926 4610 4419 2796 5062 2112 1071 3790 4220 3955 2142 4638 2832 2702 2115 2045 4085 3599 2452 5495 4767 1368 2344 4625 4132 5755 5815 2581 6259 1330 4938 815 5430 1628 3108 4342 3692 2928 1941 3714 4498 4471 4842 1822 867 3395 2587 3372 6394 6423 3728 3720 6525 4296 2091 4400 994 1321 3454 5285 2989 1755 504 5019 2629 3834 3191 6254 844 5338 615 5608 4898 2497 4482 850 5308 2763 1943 6515 5459 5556 829 4646 5258 2019 5582 1226
815
77 678686 878687
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1
2 7597 8545
74807 22362
0
3 75579860 8570575
10433 30371 14228
10433
from sys import stdin

n,m,k = [int(x) for x in stdin.readline().split()]

d = [int(x) for x in stdin.readline().split()]

if n <= 2:
  print(0)
elif d[0] == 0 or d[-1] == 0:
  print(0)
elif n % 2 == 0:
  print(0)
else:
  if m-1 >= n//2:
    print(min(k,d[0], d[-1]))
  else:
    print(0)
