410566: GYM104052 E Summer School

The Innopolis Summer School has announced its new installment. This year, the organization is a little different: there are $$$n$$$ parallels with levels ranging from $$$0$$$ to $$$n - 1$$$. Each parallel is intended to have at most $$$k$$$ students in it.

According to their past performance and training results, each student received their approximate level — also an integer from $$$0$$$ to $$$n - 1$$$.

Based on the experience of past years, the time spent studying at parallel $$$x$$$ for a student of level $$$L$$$ will be beneficial if the student's level differs from the parallel by at most $$$d + L \cdot \frac{p}{100}$$$. In other words, $$$|x - L| \le d + L \cdot \frac{p}{100}$$$.

Every day the admission system is very busy: there are many new applications and cancellations. To help students plan their summer, organizers want to figure out how many students they can invite such that everyone's participation in the summer school is beneficial.

We will describe each day as one of two types of events:

1. + L v — $$$v$$$ students of level $$$L$$$ sent their applications;
2. - L v — $$$v$$$ students of level $$$L$$$ cancelled their previous applications.

Write a program that finds the maximum number of students the organizers can invite, so everyone's participation is beneficial for them.

The first line contains integers $$$n$$$, $$$k$$$, $$$d$$$ and $$$p$$$ — the number of parallels, the maximum size of every parallel, and the constants that define if the study is beneficial, respectively ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$, $$$0 \le d \le n$$$, $$$0 \le p \le 100$$$).

The second line contains one integer $$$m$$$ — the number of days you need to process ($$$1 \le m \le 5 \cdot 10^5$$$).

The following $$$m$$$ lines contain descriptions of events of each day. Each line contains either + L v, or - L v, where $$$L$$$ is the student's level, and $$$v$$$ is the number of applications/cancellations ($$$0 \le L < n$$$, $$$1 \le v \le 10^9$$$).

Print $$$m$$$ integer: the maximum number of students the organizers can invite after every change.

Let's define $$$C$$$ as the maximum number of applications of the same level present in the system at some moment.

5 2 1 25
5
+ 4 7
- 4 3
+ 2 5
+ 3 5
- 3 2

6
4
8
8
8

5 2 1 1
6
+ 0 4
+ 1 3
- 0 2
+ 3 7
+ 4 1
- 3 6

4
6
5
10
10
7

In the first example, students of level 4 can study in parallels 2, 3, and 4. That means that after the first-day event, 6 students out of 7 can study beneficially.

In the second example, every student can only study at the parallel, which level is either equal to the student's level or differs from it by at most one.