It's almost time to say goodbye! Griffy would like to give Don Mills a parting present, and thought snow would be a good idea! However, not just any ordinary snow; sparkling stardust snow from the Alfheim Alpines! The Alfheim Alpines are strange: it is made of clouds ~R~ metres above a single bridge of length ~C~, and is covered in fog! The entire alpine range can be seen as a 2 dimensional grid (~R~ rows by ~C~ columns) in which snow falls.

Everyone knows that snow quality is the sum of the sparkling values of all snowflakes it is made of, and snow temperature is the sum of the temperatures of all the snowflakes it is made of. Unfortunately, the backpack Griffy is using is old and about to fall apart, so it cannot hold a total snow temperature that is greater than or equal to ~B~, or else it will explode. There are ~S~ snowflakes that will fall after Griffy arrives. Each stardust snowflake ~i~ has a temperature ~T_i~ and a sparkling value ~V_i~. Because of the fog, you don't always spot snowflakes from the clouds. Instead, they will come into your view ~c_i~ horizontal metres from the start of the bridge, and ~r_i~ above the height of the bridge. Griffy is not greedy, so he will only collect a maximum of ~K~ snowflakes.

Because you want to maintain relations for future programming contests, you decide to help Griffy by writing a program that will maximize the snow quality Griffy can get. Griffy starts at horizontal position ~1~ and can choose to walk up to ~M~ integer units left or right each second. For example, if ~M = 3~, then Griffy can walk any of ~-3, -2, -1, 0, 1, 2, 3~ units. Each snowflake will stay at its horizontal position and fall vertically at a rate of ~1~ metre per second. Snowflakes can ONLY be collected if the snowflake is at a height of exactly ~1~, and if Griffy is at the same horizontal position as the snowflake at the same second. Griffy can take at most ~1~ snowflake each second. Griffy can choose not to take snowflakes, and no two snowflakes will appear at the same position and time.

Input Specification

First line: 6 integers, space separated ~R~, ~C~, ~S~, ~B~, ~K~, ~M~ ~(1 \le R, C, B, K, M \le 50)~, ~(1 \le S \le R \times C)~.

Lines ~2~ to ~S+1~: 4 integers per line, space separated ~T_i~, ~V_i~, ~c_i~, ~r_i~ ~(0 \le T_i \le 50)~, ~(1 \le V_i \le 100\,000)~, ~(1 \le c_i \le C, 1 \le r_i \le R)~.

Output Specification

One integer, the maximum snow quality Griffy can get.

Sample Input

2 2 2 10 10 3
4 8 1 1
4 6 2 2

Sample Output

14

Explanation for Sample Output

There are two snowflakes within a ~2~ by ~2~ range. The maximum temperature Griffy's bag can hold is ~10~ and he will take at most ~10~ snowflakes. Griffy can walk up to ~3~ units each second. One snowflake will fall from coordinates ~(1, 1)~ with temperature ~4~ and sparkling value of ~8~. The other will fall from coordinates ~(2, 2)~ with temperature ~4~ and sparkling value ~6~.

Griffy can take the first snowflake at time 1 and then move to the right by one unit to reach the second snowflake at time 2. This way he will have a total temperature of ~4+4 = 8~ and snow quality of ~6+8 = 14~. This is the highest quality snow he will be able to get.