# Taxi

Time Limit : 1 sec, Memory Limit : 262144 KB

# ^NV[

@

ÓssPCKЂ^cPCK^NV[̓j[NȗԂ̗pĂA͋q߂邱ƂłBw̃^NV[ł́A̐lĂB

wɂ́A$N$PCKЂ̃^NV[ꂪݒuĂBeɂ$1$$N$܂ł̔ԍԂɕtĂA^NV[P䂸܂ĂB܂Aeɂ̓^NV[҂qłAꂼ̋q͂炩߂킩ĂB

PCK^NV[̉^]͒񎦊z̒Ⴂq̏ԂfA񎦊z̍qԂ邱ƂPCKЂ̔ググĂB

$i$Ԗڂ̏ɂ^]́Aq悹o܂ňȉ̍sDȏԂŉxłsƂłB

1. $i$Ԗڂ̗̏̐擪̋q^NV[ɂ̂B
2. $i$Ԗڂ̗̏̐擪̋q̏ԂfBfꂽq͗񂩂B
3. $i+1$Ԗڂ̃^NV[ɑ̃^NV[݂Ȃ΁AɈړBA$N$Ԗڂ̏ɂꍇ́Aɏoă^NV[B

Ȃ̎d́AOœꂽq̊]̕\ɁAPCKЂ̔グő剻邱ƂłBȂAP̃^NV[ɂ͍ől̋q悹邱ƂłB

^NV[̐ƁAe^NV[ɕłq̏񂪗^ꂽƂAグ̑a̍ől߂B

͈͂ȉ̌ŗ^B

$N$
$s_1$
$s_2$
$...$
$s_N$


PsڂɃ^NV[̐$N$ ($1 \leq N \leq 300,000$)^B$N$sɁA$i$Ԗڂ̃^NV[ɕłq̏$s_i$^Be$s_i$͈ȉ̌ŗ^B

$M$ $c_1$ $c_2$ ... $c_M$


ŏ̐$M$ ($1 \leq M \leq 300,000$)Ã^NV[ɕłl̐\BɑāȀ$j$Ԗڂɕłq$c_j$ ($1 \leq c_j \leq 10,000$)^BA^NV[ɕłq̑$300,000$lȉłB

グ̍ől1sɏo͂B

## ͗

3
3 8 10 1
4 7 1 2 15
3 11 8 19


## o͗

45
`
?