TopCoder

User's AC Ratio

81.8% (9/11)

Submission's AC Ratio

52.9% (9/17)

Tags

Description

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

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

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

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

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

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

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

Input Format

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

第二行輸入三個整數 X,Y0,Y1

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

  • 1N105
  • 1L,R10
  • 1Mmin(105,N(L+R))
  • 1X106
  • 1Y0Y1106
  • 1riN
  • LciR
  • ci0
  • (ri,ci)(rj,cj),ij

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