P1084

[Usaco2008 Open]Crisis on the Farm 牧场危机

[Usaco2008 Open]Crisis on the Farm 牧场危机

约翰和他的奶牛组建了一支名为“后街奶牛”的乐队，现在他们正在牧场里排练。奶牛们分成 NN 堆，每堆有 3030 只奶牛，它们一只踩在另一只的背上，叠成一座牛塔。牧场里还有 MM 个高高的草垛。

作为一名出色的指挥家，约翰可以通过口哨指挥奶牛们移动。他的口哨有四种音调，分别能使所有牛塔向东、南、西、北移动一格。若牛塔当前位于 (x,y)(x,y)，则指令 E、W、N、S 分别会将其移动到 (x+1,y)(x+1,y)、(x−1,y)(x-1,y)、(x,y+1)(x,y+1)、(x,y−1)(x,y-1)。

每当一座牛塔到达草垛所在的格子时，牛塔最上方的奶牛就会跳到草垛上，并且不再下来；其余奶牛仍保持塔状，停留在草垛所在的格子中。当牛塔只剩下 11 只奶牛时，这只奶牛也会跳到草垛上，此后该牛塔便不再移动。

突然，邻居家的奶缸爆炸了，滚滚而下的牛奶正向约翰的牧场涌来，不久就会淹没整个牧场。约翰必须立刻用口哨指挥牛塔，让尽可能多的奶牛跳到草垛上。已经跳上草垛的奶牛不会被淹死。

洪水到来之前，约翰必须恰好吹响 KK 次口哨。每次吹哨后，所有仍有奶牛的牛塔都会按照对应方向移动一格，随后计算到达草垛的牛塔所救出的奶牛。

请计算最多能够挽救多少只奶牛，并给出一种能够达到该最大值的口哨指令序列。指令序列使用 E、W、S、N 分别表示东、西、南、北。如果有多种长度为 KK 的指令序列能够挽救最多的奶牛，请输出其中字典序最小的序列。

输入格式

第一行输入三个整数 NN、MM、KK，分别表示牛塔数量、草垛数量和约翰必须吹响口哨的次数。

接下来 NN 行，每行输入两个整数 XiX_i、YiY_i，表示一座牛塔所在的位置 (Xi,Yi)(X_i,Y_i)。

再接下来 MM 行，每行输入两个整数 XiX_i、YiY_i，表示一个草垛所在的位置 (Xi,Yi)(X_i,Y_i)。

输出格式

第一行输出一个整数，表示最多能够挽救的奶牛数量。

第二行输出一个长度恰好为 KK、仅由 E、N、S、W 组成的字符串。在所有能够挽救最多奶牛的序列中，输出字典序最小的序列。

样例输入

3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7

样例输出

6
EEE

样例解释

连续使用 33 次向东移动的口哨指令，此后洪水到达牧场。共有 66 个草垛分别救下了 11 只奶牛，因此总共救出了 66 只奶牛。

数据范围

  • 1≤N≤10001\le N\le 1000；
  • 1≤M≤10001\le M\le 1000；
  • 1≤K≤301\le K\le 30；
  • 1≤Xi≤10001\le X_i\le 1000；
  • 1≤Yi≤10001\le Y_i\le 1000；
  • 所有草垛所在格子的坐标两两不同。

来源与许可

本题为 USACO 2008 Open 试题「牧场危机」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7

输出

6
EEE