Description

John and his cows have formed a band called "Backstreet Cows," and they are rehearsing on the pasture. The cows are grouped into $N$ piles. In each pile, $30$ cows stand one on another, forming a tower. There are also $M$ tall haystacks on the pasture.

As a skilled conductor, John can use four whistle tones. Each tone makes all towers move one cell in one of the four directions: east, west, south, or north.

Each time a tower reaches a cell that contains a haystack, the cow at the top of the tower jumps onto the haystack and stays there, while the remaining cows continue to stand as a tower on that cell. When only one cow remains in a tower, that cow also jumps onto the haystack.

Suddenly, the neighbor’s milk tank explodes. A torrent of milk is rushing toward John’s pasture and will flood it soon. John must act immediately and use whistle tones to save as many cows as possible. Cows on haystacks will not drown.

John has $K$ whistle blows left. How many cows can he save at most? Compute the maximum number of cows that can be saved, and a sequence of whistle tones to achieve it. The sequence is represented by $\mathtt{E, W, S, N}$ for east, west, south, and north. If multiple sequences achieve the maximum, output the lexicographically smallest one.

Input Format

• The first line contains three positive integers $N, M, K$.
• The next $N$ lines each contain two positive integers $X_i, Y_i$, the coordinates $(X_i, Y_i)$ of a cow pile.
• The next $M$ lines each contain two positive integers $X_i, Y_i$, the coordinates $(X_i, Y_i)$ of a haystack.

Output Format

• The first line contains an integer, the maximum number of cows that can be saved.
• The second line contains a string of length $K$ that is the lexicographically smallest whistle tone sequence achieving that maximum.

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

6 
EEE 

Hint

Sample explanation:

After $3$ whistles, $3$ haystacks each save one cow.

Constraints:

For $100\%$ of the testdata, $1 \le K \le 30$, $1 \le N, M, X_i, Y_i \le 1000$.

Translated by ChatGPT 5