After years of deliberation, you have finally decided to get a job for the fast growing startup called Oober Treats! Oober Treats has decided that rather than having children running around streets on Halloween, the candy will instead be delivered right to their door!

On Halloween night, you will drive a delivery truck that has ~F~ units of fuel, and will have ~N~ different candy delivery routes to choose from. Each route takes ~f_i~ units of fuel and allows you to earn cash each time you complete the route. The first time you complete the ~i^{th}~ route, you will earn ~a_i~ units of cash. For every additional time you complete the route, you will earn ~b_i~ units of cash. However, not wanting you to become too bored at the job, your delivery company will only let you complete the same route at most ~K~ times. If you choose which delivery routes to complete optimally, what is the maximum amount of cash you can earn without running out of fuel?

Of course the cash you earn changes based on the level of demand of the customers. Since Oober Treats did not have enough money to hire good app developers, the prices were hard-coded and each price change will require an update to the app. Sometimes, the developers will realize they need to revert to a previous version of the app before making a change.

There will be a total of ~Q~ app changes over time. The ~i^{th}~ change will modify the version of the app after the ~j_i^{th}~ change (or the initial version of the app if ~j_i = 0~) so that the ~x_i^{th}~ delivery route now earns ~c_i~ units of cash the first time the route is completed, and ~d_i~ units of cash for each additional completion. After each change, print the maximum amount of cash you can earn before running out of fuel.

Constraints

~1 \le F, Q, K \le 3\,000~
~1 \le N \le 500~
~1 \le f_i \le 3\,000~ for ~1 \le i \le N~
~1 \le a_i, b_i \le 10^9~ for ~1 \le i \le N~
~1 \le c_i, d_i \le 10^9~ for ~1 \le i \le Q~
~0 \le j_i < i~ for ~1 \le i \le Q~
~1 \le x_i \le N~ for ~1 \le i \le Q~

Input Specification

The first line of input contains ~4~ integers, ~N, Q, F, K~.

The next ~N~ lines describe the initial candy delivery routes. Each line contains ~3~ integers, ~f_i, a_i, b_i~.

The next ~Q~ lines describe the app changes. Each line contains ~4~ integers, ~j_i, x_i, c_i, d_i~.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output ~Q~ lines. On the ~i^{th}~ line, output the maximum amount of cash you can earn before running out of fuel after the ~i^{th}~ change of the app.

Sample Input

2 2 5 2
2 5 2
1 3 1
0 2 4 3
0 1 7 3

Sample Output

12
13

Sample Explanation

After the first change to the app, we can complete the first route once, and the second route twice. This takes ~2 + 1 + 1 = 4~ units of fuel and earns ~5 + 4 + 3 = 12~ units of cash.

After the second change to the app, we can complete the first route twice, and the second route once. This takes ~2 + 2 + 1 = 5~ units of fuel and earns ~7 + 3 + 3 = 13~ units of cash.

Note that ~K = 2~, so we cannot complete the same route more than twice.