คุณได้เกมสำหรับโทรทัศน์ที่บริษัท JOI วางจำหน่ายมาเกมหนึ่ง เป็นเกมที่ทำออกมาได้ดีพอสมควร และคุณเล่นอย่างสนุกสนานทุกวัน

วันหนึ่ง ด่านที่เหล่าเกมเมอร์เรียกกันว่า “เลเซอร์” ปรากฏขึ้น ดูเหมือนว่าด่านนี้จะยากมาก แม้แต่เกมเมอร์ฝีมือดีก็มีโอกาสผ่านได้เพียงเล็กน้อย หลังจากลองเล่นด่านนี้หลายครั้ง คุณสังเกตว่าอาจผ่านได้ด้วยการตัดสินใจอย่างรวดเร็วมาก จึงคิดว่าจะเขียนโปรแกรมมาช่วยจัดการ

ด่านเลเซอร์มีฉากเป็นพื้นที่ที่มีกำแพงป้องกัน $N$ แห่ง ฉากเป็นรูปสี่เหลี่ยมผืนผ้า แบ่งออกเป็นช่องสี่เหลี่ยมจัตุรัสขนาด $1 \times 1$ แต่ละช่องแทนด้วย $(x,y)$ โดย $x$, $y$ เป็นจำนวนเต็มไม่ติดลบ ช่อง $(0,0)$ อยู่มุมล่างซ้าย และช่อง $(x,y)$ คือช่องที่อยู่ทางขวา $x$ ช่องและขึ้นไป $y$ ช่องจาก $(0,0)$

เมื่อด่านเริ่ม ศัตรูจะปรากฏตัวและโจมตี โดยมีการโจมตี $M$ ครั้งตามลำดับ ในการโจมตีครั้งที่ $j$ ศัตรูยิงเลเซอร์เป็นเส้นตรงจากช่อง $(P_j,N+1)$ ไปทางช่อง $(P_j,0)$

กำแพงแต่ละแห่งวางอยู่บนช่องที่ต่อเนื่องกันและมีพิกัด $y$ เท่ากัน กำแพงที่ $i$ ($1 \le i \le N$) เป็นรูปสี่เหลี่ยมผืนผ้าที่มีความกว้างแนวนอน $B_i-A_i+1$ และความสูง $1$ เมื่อเริ่มด่านจะครอบคลุมช่องตั้งแต่ $(A_i,i)$ ถึง $(B_i,i)$ คุณสามารถขยับกำแพงไปทางซ้ายหรือขวาได้กี่ครั้งก็ได้ ก่อนการโจมตีครั้งแรกและระหว่างการโจมตีแต่ละครั้ง ในการขยับหนึ่งครั้ง คุณสามารถขยับกำแพงหนึ่งแห่งไปทางขวาหนึ่งช่องหรือทางซ้ายหนึ่งช่อง

เลเซอร์จะอ่อนกำลังลงเมื่อชนกำแพง คุณต้องการให้เลเซอร์อ่อนกำลังที่สุด โดยขยับกำแพงให้เลเซอร์ชนกำแพงทุกแห่ง

คุณต้องการให้จำนวนครั้งที่ขยับกำแพงในด่านนี้น้อยที่สุดเท่าที่จะเป็นไปได้

งานที่ต้องทำ

กำหนดตำแหน่งเริ่มต้นของกำแพงแต่ละแห่งและตำแหน่งการโจมตีแต่ละครั้งของศัตรู จงหาจำนวนครั้งน้อยที่สุดที่ต้องขยับกำแพงแต่ละแห่ง เพื่อให้เลเซอร์ทุกลำชนกำแพงทุกแห่ง

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกประกอบด้วยจำนวนเต็ม $N$, $M$ คั่นด้วยช่องว่าง หมายความว่าด่านนี้มีกำแพง $N$ แห่ง และศัตรูโจมตี $M$ ครั้ง
• บรรทัดที่ $i$ ($1 \le i \le N$) จาก $N$ บรรทัดถัดไปประกอบด้วยจำนวนเต็ม $A_i$, $B_i$ คั่นด้วยช่องว่าง หมายความว่าเมื่อเริ่มด่าน กำแพงที่ $i$ วางอยู่ตั้งแต่ช่อง $(A_i,i)$ ถึง $(B_i,i)$
• บรรทัดที่ $j$ ($1 \le j \le M$) จาก $M$ บรรทัดถัดไปประกอบด้วยจำนวนเต็ม $P_j$ หมายความว่าในการโจมตีครั้งที่ $j$ ศัตรูยิงเลเซอร์เป็นเส้นตรงจากช่อง $(P_j,N+1)$ ไปทางช่อง $(P_j,0)$

ข้อมูลส่งออก

พิมพ์ $N$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน บรรทัดที่ $i$ ($1 \le i \le N$) ให้พิมพ์จำนวนครั้งน้อยที่สุดที่ต้องขยับกำแพงที่ $i$

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $1 \le N \le 200\,000$
• $1 \le M \le 200\,000$
• $0 \le A_i \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $0 \le P_j \le 1\,000\,000\,000$ ($1 \le j \le M$)

งานย่อย

งานย่อย 1 [10 คะแนน]

• เป็นไปตาม $N=1$

งานย่อย 2 [45 คะแนน]

• เป็นไปตาม $A_i=0$ ($1 \le i \le N$)

งานย่อย 3 [45 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

ข้อมูลส่งออก 1

5
10
1
7

หมายเหตุ

สำหรับข้อมูลนำเข้านี้ วิธีหนึ่งที่ทำให้จำนวนครั้งการขยับกำแพงน้อยที่สุดเป็นดังนี้

• ก่อนการโจมตีครั้งแรก ขยับกำแพงที่ $1$ ไปทางขวา $3$ ครั้ง ขยับกำแพงที่ $2$ ไปทางขวา $2$ ครั้ง ไม่ขยับกำแพงที่ $3$ และขยับกำแพงที่ $4$ ไปทางซ้าย $2$ ครั้ง
• ก่อนการโจมตีครั้งที่สอง ไม่ขยับกำแพงที่ $1$ ขยับกำแพงที่ $2$ ไปทางซ้าย $2$ ครั้ง ไม่ขยับกำแพงที่ $3$ และขยับกำแพงที่ $4$ ไปทางซ้าย $2$ ครั้ง
• ก่อนการโจมตีครั้งที่สาม ไม่ขยับกำแพงที่ $1$ ขยับกำแพงที่ $2$ ไปทางซ้าย $1$ ครั้ง ไม่ขยับกำแพงที่ $3$ และขยับกำแพงที่ $4$ ไปทางซ้าย $1$ ครั้ง
• ก่อนการโจมตีครั้งที่สี่ ขยับกำแพงที่ $1$ ไปทางขวา $2$ ครั้ง ขยับกำแพงที่ $2$ ไปทางขวา $5$ ครั้ง ขยับกำแพงที่ $3$ ไปทางขวา $1$ ครั้ง และขยับกำแพงที่ $4$ ไปทางขวา $2$ ครั้ง

ด้วยวิธีนี้ จะขยับกำแพงที่ $1$ ทั้งหมด $5$ ครั้ง กำแพงที่ $2$ ทั้งหมด $10$ ครั้ง กำแพงที่ $3$ ทั้งหมด $1$ ครั้ง และกำแพงที่ $4$ ทั้งหมด $7$ ครั้ง

เมื่อเริ่มด่าน → การโจมตีครั้งที่ 1 → การโจมตีครั้งที่ 2 → การโจมตีครั้งที่ 3 → การโจมตีครั้งที่ 4

ข้อมูลนำเข้า 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

ข้อมูลส่งออก 2

34
178
13
6
18
0
36