Maximizing Additional Starting Points

In the Byteotian driving licence exam the testing area is made up of n straight, parallel, north‐oriented streets. Each street is exactly m meters long and numbered from 1 (the westernmost) to n (the easternmost). In addition, there are p pre‐existing horizontal streets connecting pairs of adjacent north–south streets. Each horizontal street is unidirectional (either east–oriented or west–oriented). Note that an east–oriented street and a west–oriented street may overlap on the same gap, forming a bidirectional connection.

The examination starts at the beginning of one north–oriented street (the starting point) and ends at the end of another. The examiner always chooses as starting point a street from which it is possible to drive (following the allowed directions) to the endpoint of every north–oriented street. The existence of a valid path from a starting street i to any other street j depends solely on the availability of connecting horizontal streets between adjacent streets. In particular, if we denote by

• $A_r=\begin{cases}0,&\text{if an east–oriented road exists between street }r\text{ and }r+1,\\1,&\text{otherwise,}\end{cases}$ for each gap \(r=1,2,\dots,n-1\), and
• $B_r=\begin{cases}0,&\text{if a west–oriented road exists between street }r\text{ and }r+1,\\1,&\text{otherwise,}\end{cases}$ for each gap \(r=1,2,\dots,n-1\),

then a north–oriented street i (\(1 \le i \le n\)) is a valid starting point if and only if:

• For every gap \(r\) with \(1 \le r \le i-1\) we have \(B_r=0\) (i.e. all needed west–directed roads exist), and
• For every gap \(r\) with \(i \le r \le n-1\) we have \(A_r=0\) (i.e. all needed east–directed roads exist).

The board has decided that at most k new horizontal streets (each connecting two adjacent north–oriented streets and oriented in either east or west direction) may be built. These new streets can be built arbitrarily (choosing the appropriate direction when built) and are meant to make additional streets become valid starting points. Your task is to choose up to k gaps in which to build new roads (if needed) so as to maximize the number of new potential starting points. That is, if a street was already a valid starting point before building the new roads, it is not counted; only those that become valid as a result of constructing new streets are counted.

Input/Output summary:

• Input: A description of the testing area and the integer k. The first line contains four integers n m p k (n = number of north–oriented streets, m = length of each street in meters, p = number of pre–existing horizontal streets, k = maximum number of new horizontal streets). Each of the next p lines contains a gap index r (an integer between 1 and n-1) and a character ('E' or 'W') indicating the orientation of a pre–existing horizontal street connecting street r and r+1.
• Output: A single integer indicating the greatest possible number of additional potential starting points that can be obtained by adding no more than k new horizontal streets.

Note: For any chosen set of new roads, if we build a new road in gap r then it will supply the missing connection in the corresponding direction (either east if \(A_r=1\) or west if \(B_r=1\)).

inputFormat

The input begins with a line containing four integers: n m p k (\(1 \le n \le \text{some upper bound}\); \(m\) is the length of each north–oriented street; \(p\) is the number of pre–existing horizontal streets; \(0 \le k \le \text{some upper bound}\)). Each of the following p lines contains an integer r (with \(1 \le r \le n-1\)) and a character (E or W), indicating that there is a horizontal street connecting street r and r+1 with the given orientation.

outputFormat

Output a single integer – the maximum number of new potential starting points (i.e. north–oriented streets that become valid starting points after adding up to k new horizontal streets) that can be achieved.

sample

4 3 5 1
1 E
2 W
2 E
3 E
3 W

4