TopCoder

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

55.6% (5/9)

Tags

Description

快樂列車是一個年度活動,旨在讓乘客在乘坐這列火車遊遍全國的過程中感到快樂。由於這個問題與活動的其他細節無關,這裡將不作介紹。我們只關注火車的設計。

火車內部有 $N$ 排座位和一條走道,每排座位的走道左側有 $L$ 個座位,右側有 $R$ 個座位。

明天將會有 $M$ 名乘客登上這列火車。所有乘客都購買了對號座的票,也就是說他們會有自己的專屬座位。我們可以假設售票系統運行良好,所有的對號座位都會不一樣。

列車長提姆知道每位乘客的對號座位,並希望估算所有乘客坐定所需的時間。他考慮了以下的上車模型:乘客 $i$ 將是第 $i$ 位登上火車的乘客。在時間點 $0$,第 $1$ 位乘客站在第一排的走道上。每當上一位乘客坐下時,下一位乘客會恰好出現在第一排的走道上。一位乘客從第 $i$ 排的走道走到第 $i+1$ 排的走道需要耗時 $X$ 秒。移動到同排相鄰的空座位需要 $Y_0$ 秒,如果不是空座位的話,則需要 $Y_1$ 秒,因為要避免碰到已經入坐的乘客。同一排中,走道和其左右側的第一個座位視為相鄰。當一位乘客走到自己座位時,便會坐下。每位乘客只會坐到自己的座位上,而坐下的時間可以忽略不計。注意,乘客只有在走道上時才能在排與排之間移動。

$N=6,L=3,R=2$ 的座位(綠色)和走道(紅色)示意圖,其中白色圓圈代表乘客。

在示意圖中,剛登上火車的乘客需要花 $X+X+Y_0+Y_1+Y_0$ 秒才能抵達他的座位(第三排走道左側第三個座位)。

提姆想知道在這個模型下,所有乘客坐定需要多長的時間。請幫助提姆計算出答案。

Input Format

第一行輸入四個整數 $N,L,R,M$。

第二行輸入三個整數 $X,Y_0,Y_1$。

接下來輸入 $M$ 行,其中的第 $i$ 行輸入兩個整數 $r_i,c_i$。如果 $c_i<0$,則代表第 $i$ 位乘客的對號座為第 $r_i$ 排走道左側第 $|c_i|$ 個座位。否則,代表第 $i$ 位乘客的對號座為第 $r_i$ 排走道右側第 $c_i$ 個座位。

  • $1 \leq N \leq 10^ 5$
  • $1 \leq L,R \leq 10$
  • $1 \leq M \leq \min(10^ 5,N(L+R))$
  • $1 \leq X \leq 10^ 6$
  • $1 \leq Y_0 \leq Y_1 \leq 10^ 6$
  • $1 \leq r_i \leq N$
  • $-L \leq c_i \leq R$
  • $c_i \neq 0$
  • $(r_i,c_i) \neq (r_j,c_j),\forall i\neq j$

Output Format

輸出一行,這行輸出一個整數,代表在提姆的模型下,所有乘客入座所需的總秒數。

Sample Input 1

6 3 2 9
1 5 13
6 1
3 -1
3 -3
2 2
5 2
2 1
3 -2
4 -2
1 -3

Sample Output 1

121

Sample Input 2

1 5 5 2
1000000 1 100
1 2
1 4

Sample Output 2

105

Sample Input 3

1 5 5 2
1000000 1 100
1 4
1 2

Sample Output 3

6

Sample Input 4

100 10 10 1
1 1000 45510
10 -10

Sample Output 4

10009

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~10 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 1 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2