410054: GYM103934 B Tuk-Tuk Express

The city of Sharm el-Sheikh is full due to the ICPC World Finals, the largest event in the world. One of University of São Paulo competitors, Lucas _Lucas3h_ Harada, is on the city center buying souvenirs. Unfortunately, for him and the for rest of his team, the streats are jammed with traffic, and, guess what, the World Finals will take place today!

But fear no more, because the organizers thought about everything. The ICPC Committee hired Tuk-Tuks to take the competitors from the city center to the hotel.

They hired three companies to do the job. As one should expect of an event of this importance, there is an infinity number of Tuk-Tuks of each company, and one arrives immediately after one leaves. The Tuk-Tuks of each company take $$$t_1$$$, $$$t_2$$$, and $$$t_3$$$ minutes respectively to go from the city center to the hotel. Besides that, each one can carry up to $$$C$$$ passengers. Each Tuk-Tuk laves the city center when at least one of the following conditions is fulfilled

1. $$$C$$$ passengers have boarded;
2. $$$X$$$ minutes have passed after the boarding started.

The second rule exists to avoid some competitors waiting for too long. Notice that this implies that one Tuk-Tuk may even make a trip with no passengers! Also notice that each company has it's own separated service.

The world finals will start in $$$T$$$ minutes, and right now, at time zero, there is one Tuk-Tuk of each company leaving the city center. You may assume that each one of these Tuk-Tuks reaches the hotel in time to the competition.

Lucas needs your help, he wants to know what is the maximum amount of time he can spent at the city center without getting late to the World Finals! For some unknown reason he knows that there $$$N$$$ competitors at the city center and each of them will embark in a Tuk-Tuk of company $$$c_i$$$ at time $$$d_i$$$, and he sent this list to you.

You may assume that, if Lucas arrive at the same time as any other competitor, he will board before them.

The first line contains four space separated integers $$$C, X, T, N$$$ ($$$1 \leq C, N \leq 10^5$$$ and $$$1 \leq X, T \leq 10^9$$$), as described above.

The second line contains three space separated integers $$$t_1, t_2, t_3$$$ ($$$1 \leq t_1, t_2, t_3 \leq T$$$), the time each Tuk-Tuk takes to go from the city center to the hotel.

The next $$$N$$$ lines contains two space separated integers $$$d_i$$$ ($$$1 \leq d_i \leq 10^9$$$) and $$$c_i$$$ ($$$1 \leq c_i \leq 3$$$), the time contestant $$$i$$$ boards a Tuk-Tuk from company $$$c_i$$$.

Print one integer, the maximum number of minutes Lucas can spend buying souvenirs at the city center.

4 5 20 15
6 7 8
4 1
5 2
6 3
7 1
8 2
9 3
10 1
11 2
12 3
13 1
14 2
15 3
16 1
17 2
18 3

10

1 5 20 6
9 23 25
1 1
5 1
8 1
10 1
12 1
13 1

11