SPOJ in Armenian

Ֆլատլանդիայում կա միայն մեկ փողոց՝ այն էլ իրենից ներկայացնում է իդեալական շրջանագիծ: Փողոցն ունի  1000000 միավոր երկարություն, փողոցի ամենահյուսիսային կետը ունի  0
կոորդինատը (փողոցի կոորդինատական համակարգի սկզբնակետը  0 կետն է, մնացած կետերը կոորդինատավորվում են ըստ սկզբնակետից, փողոցի երկայնքով և ժամսլաքին հակառակ
ուղղությամբ, ունեցած միավոր հեռավորությամբ: Ֆլատլանդիայում ապրում են  N (1 ≤ N ≤ 1000) ընտանիքներ, որոնցից յուրաքանչյուրը ունի ուղիղ մեկ տուն այդ փողոցում (չկան երկու տներ
փողոցի նույն կոորդինատում): Տները գտնվում են ամբողջաթիվ կոորդինատներում: Եկել է նախագահական ընտրությունների ժամանակը, և կառավարությունը փորձում է անել ամեն ինչ
որպեսզի բնակիչների համար լինի մաքսիմալ հարմարավետ: Կառավարությունն ունի հնարավորություն բացելու ընդամենը  M (1 ≤ M ≤ 1000) ընտրական տեղամասեր: Յուրաքանչյուր
տեղամաս պետք է տեղակայված լինի փողոցի որևէ ամբողջաթիվ կոորդինատում (տեղամասը կարող է տեղակայվել նաև այն կոորդինատում որտեղ տուն կա): Յուրաքանչյուր տան
«Հարմարավետություն» կանվանենք այդ տնից մինչև իրեն ամենամոտ ընտրական տեղամաս եղած հեռավորությունը: «Ընդհանուր հարմարավետություն» կանվանենք բոլոր տների
«հարմարավետություն»-ներից ամենամեծը: Ձեր խնդիրն է գտնել ամենափոքր հնարավոր «Ընդհանուր հարմարավետության» արժեքը (տեղամասերը կարող եք տեղակայել ձեր
հայեցողությամբ):

Մուտք„

Մուտքային ֆայլի առաջին տողում գրված է  N բնական թիվը: Հաջորդ  N տողերում գրված են տների կոորդինատները: Հաջորդ տողում գրված է  M բնական թիվը:

Ելք„

Ելքային ֆայլը պետք է պարունակի ամենափոքր հնարավոր «Ընդհանուր հարմարավետության» արժեքը:

Օրինակ

Մուտք„.
4
0
67000
77000
68000
2

Ելք„.
5000