Crisis on the Farm

Farmer John and his herd of exotic dancing cows are rehearsing his new musical, "The Street Cow Named Desire". Midway through rehearsal the cows are arranged into $N$ ($1 \le N \le 1000$) stacks of exactly 30 cows each, one cow standing on the back of another (they are remarkably talented cows). The pasture also holds $M$ ($1 \le M \le 1000$) haystacks at separate locations. One possible layout:

                8 .........
                7 ....CH.H.         C = stack of 30 cows
                6 .........
                5 .........         H = haystack
                4 ..C.HH...
                3 .........
                2 .....C.HH
                1 .........
                  123456789

As conductor, Farmer John has four whistles. One orders the cow at the bottom of every stack to move one unit north (carrying every cow above it); the others order a move south, east, or west. A single whistle moves all stacks at once in the same direction.

Whenever a stack enters a grid cell that contains a haystack, the cow on top of that stack (even if the stack has height one) jumps onto the haystack, while the rest of the stack keeps moving into the haystack's cell. So a stack that enters 30 haystacks — the same one repeatedly, or different ones — is emptied completely, every cow safely on a haystack (or on a cow already on a haystack). A haystack can hold any number of cows.

Suddenly a milk tank on the neighboring farm bursts and a tidal wave of milk rushes toward the pasture. Cows standing on a haystack are safe; every other cow is lost. Farmer John can blow his whistle exactly $K$ ($1 \le K \le 30$) more times before the wave arrives.

Given $K$ and the positions ($1 \le X_i \le 1000$, $1 \le Y_i \le 1000$) of the $N$ cow stacks and $M$ haystacks (no haystack starts with cows on it, and no stack shares a cell with a haystack), determine the largest number of cows that can be saved and output a whistle sequence that achieves it. Directions are written 'E' (east), 'N' (north), 'W' (west), 'S' (south). Among all sequences that save the maximum number of cows, output the lexicographically smallest one. Stacks may move to any cell, including cells outside the pasture.

• Line 1: three space-separated integers $N$, $M$, and $K$.
• Lines 2 to $N+1$: two space-separated integers $X_i$ and $Y_i$, the location of a stack of 30 cows.
• Lines $N+2$ to $N+M+1$: two space-separated integers $X_i$ and $Y_i$, the location of a haystack.

• Line 1: a single integer, the maximum number of cows that can be saved.
• Line 2: exactly $K$ characters, the lexicographically smallest sequence of whistle commands that saves that many cows.

Since one whistle moves every stack in the same direction, only the cumulative displacement matters: a stack saves a cow each time that displacement lands it on a haystack. Sending all stacks straight in one direction can sweep several haystacks at once, and revisiting the same haystack cell saves another cow each time.