n,*b=`dd`.split.map &:to_i;_=b.pop(n).sort.map{|v|v*M=2000};p (1..n).map{a=_.dup;b.rotate!.map{|l|m=a.shift+l/2*M+1;a.insert(a.bsearch_index{|v|v>m}||-1,m)};a.map{|v|v%M}.max}.min