#include<stdio.h>
#define wb(x) ((x)<0?-(x):(x))
int coord[20], pos[1<<16];
long long min[1<<16], max[1<<16];
int main()
{
int n, d, i, j, k, m, a, b;
long long x;
m = 1<<(d-1); // 2^(d-1)
for(i = 0; i < m; ++i) // preprocessing; calculating all positions on which Gray numbers change
{
min[i] = 1e15;
max[i] = -1e15;
if(i)
{
pos[i] = 1; a = i^(i>>1); b = (i-1)^((i-1)>>1); k = a^b; // formulas for n-th Gray numbers
while(k%2 == 0) // given power of 2 calculates the exponent
++pos[i],
k >>= 1;
if(b < a) // negative numbers for change from bit 1 to 0
pos[i] = -pos[i];
}
}
while(n--)
{
for(j = 0; j < d; ++j)
x = 0;
for(k = 0; k < d; ++k) // calculate the first sum
x += coord[k];
if(x < min[0])
min[0] = x;
if(x > max[0])
max[0] = x;
for(j = 1; j < m; ++j) // check all combinations of sums
{
x += 2*coord[wb(pos[j])-1]*(pos[j] > 0 ? 1 : -1); // add or subtract one element
if(x < min[j])
min[j] = x;
if(x > max[j])
max[j] = x;
}
}
x = -1;
for(i = 0; i < m; ++i)
if(wb(max[i]-min[i]) > x)
x = wb(max[i]-min[i]);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KCiNkZWZpbmUgd2IoeCkgKCh4KTwwPy0oeCk6KHgpKQoKaW50IGNvb3JkWzIwXSwgcG9zWzE8PDE2XTsKbG9uZyBsb25nIG1pblsxPDwxNl0sIG1heFsxPDwxNl07CgppbnQgbWFpbigpCnsKCWludCBuLCBkLCBpLCBqLCBrLCBtLCBhLCBiOwoJbG9uZyBsb25nIHg7CgkKCXNjYW5mKCIlZCVkIiwgJmQsICZuKTsKCW0gPSAxPDwoZC0xKTsgLy8gMl4oZC0xKQoJZm9yKGkgPSAwOyBpIDwgbTsgKytpKSAvLyBwcmVwcm9jZXNzaW5nOyBjYWxjdWxhdGluZyBhbGwgcG9zaXRpb25zIG9uIHdoaWNoIEdyYXkgbnVtYmVycyBjaGFuZ2UKCXsKCQltaW5baV0gPSAxZTE1OwoJCW1heFtpXSA9IC0xZTE1OwoJCWlmKGkpCgkJewoJCQlwb3NbaV0gPSAxOyBhID0gaV4oaT4+MSk7IGIgPSAoaS0xKV4oKGktMSk+PjEpOyBrID0gYV5iOyAvLyBmb3JtdWxhcyBmb3Igbi10aCBHcmF5IG51bWJlcnMKCQkJd2hpbGUoayUyID09IDApIC8vIGdpdmVuIHBvd2VyIG9mIDIgY2FsY3VsYXRlcyB0aGUgZXhwb25lbnQKCQkJCSsrcG9zW2ldLAoJCQkJayA+Pj0gMTsKCQkJaWYoYiA8IGEpIC8vIG5lZ2F0aXZlIG51bWJlcnMgZm9yIGNoYW5nZSBmcm9tIGJpdCAxIHRvIDAKCQkJCXBvc1tpXSA9IC1wb3NbaV07CgkJfQoJfQoJd2hpbGUobi0tKQoJewoJCWZvcihqID0gMDsgaiA8IGQ7ICsraikKCQkJc2NhbmYoIiVkIiwgJmNvb3JkW2pdKTsKCQl4ID0gMDsKCQlmb3IoayA9IDA7IGsgPCBkOyArK2spIC8vIGNhbGN1bGF0ZSB0aGUgZmlyc3Qgc3VtCgkJCXggKz0gY29vcmRba107CgkJaWYoeCA8IG1pblswXSkKCQkJbWluWzBdID0geDsKCQlpZih4ID4gbWF4WzBdKQoJCQltYXhbMF0gPSB4OwoJCWZvcihqID0gMTsgaiA8IG07ICsraikgLy8gY2hlY2sgYWxsIGNvbWJpbmF0aW9ucyBvZiBzdW1zCgkJewoJCQl4ICs9IDIqY29vcmRbd2IocG9zW2pdKS0xXSoocG9zW2pdID4gMCA/IDEgOiAtMSk7IC8vIGFkZCBvciBzdWJ0cmFjdCBvbmUgZWxlbWVudAoJCQlpZih4IDwgbWluW2pdKQoJCQkJbWluW2pdID0geDsKCQkJaWYoeCA+IG1heFtqXSkKCQkJCW1heFtqXSA9IHg7CgkJfQoJfQoJeCA9IC0xOwoJZm9yKGkgPSAwOyBpIDwgbTsgKytpKQoJCWlmKHdiKG1heFtpXS1taW5baV0pID4geCkKCQkJeCA9IHdiKG1heFtpXS1taW5baV0pOwoJcHJpbnRmKCIlbGxkXG4iLCB4KTsKCXJldHVybiAwOwp9