In the olden times there was a young emperor who was the bravest, wisest, richest, most handsome in the whole world. He had proven himself in endless of battles, quests, and victories but his court was not happy because he had not appointed a queen yet. However, choosing a queen was not easy because of his high status and standard, the emperor wanted a girl not only beautiful but smart and kind as well. Lightning Knight - that was the young Emperor's name - sent his most trusted knights out to seek for a girl like that; and after a long time searching, the men brought back two of the most beautiful and intelligent girls in all the lands. They were two princess sisters from a faraway land. The older sister - Van Trinh - was mysterious and beautiful like the moon, while Thuy Linh - the younger one - was bright and lovely as the sun. They were both famous for being kind, gentle, and intelligent to their people, and as many girls before them, they both fell truly, madly, deeply in love with the handsome emperor at first sight.

Now, the Emperor had to face the hardest test of all: to pick just one in these two sisters to become his rightful and beloved queen and lay the world under her feet. After countless sleepless nights, the Emperor sought out a just solution. He thought of a riddle and announced to the two princesses and the court that he would marry the first one who bring the right answer to his desk.

At the same time with the above event, the Emperor had just won the most important battle to unite all the lands in the world. That was two good news in such a short time. Being the rich and generous emperor he was, the Emperor wanted to reward to all the brave and loyal generals with boxes of gold. The distribution was not easy and that's why he chose it as the riddle for Van Trinh and Thuy Linh. Centuries has passed since then, the Emperor and queen might have died and their romance might have been forgotten from our world, but the riddle still remains as one of the hardest tasks in the ancient books.

The Emperor wants to reward N boxes of gold to M generals. The i-th box has the value of A_i. Now the Emperor wants to give N boxes to M generals so that the difference of gold between the general who receives the most gold and the general who receives the least gold is as small as possible. Note: a general can receive more than one box, and he must receive the whole box (i.e.: not half or 1/3 of box).

The 1st line contains three positive integers N, M and K (N ≤ 10000, M ≤ 1000 and N ≥ M). K is the maximum result that the emperor accepts. The 2nd line contains N positive integers 0 < A₁, A₂, …, A_N ≤ 1000.

The 1st line contains one integer which is the minimum difference your program can find. In the next M lines, the i-th line contains the index of boxes rewarded to the i-th general.