C. Дима ба шат

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Димад $n$ гишгүүртэй шат байдаг. Эхний гишгүүр нь $a_1$ өндөртэй. Хоёр дахь гишгүүр нь $a_2$ өндөртэй гэх мэт сүүлийн гишгүүрийн өндөр нь $a_n$ ($1$≤$a_1$≤$a_2$≤...≤$a_n$).

Дима шатаараа тоглохоор шийджээ. Тэр шатныхаа дээрээс хайрцагнууд унагаж байв. $i$-р хайрцаг нь $w_i$ өргөн $h_i$ өндөртэй. Дима хайрцагаа яг эгц доош нь шатны эхний $w_i$ гишгүүрүүд дээр унагаж байв. Унагалт болгонд доорх хоёр үзэгдлийн аль нэг нь тохиолдоно:

  • Хайрцагны доод хэсэг гишгүүр дээр унах.
  • Хайрцагны доод хэсэг өмнөх унагасан хайрцагны дээр унах.

Зөвхөн сууриар унахыг л авч үзэх бөгөөд ямар нэгэн байдлаар булан эсвэл хажуу талаар наалдахыг тооцохгүй. Нарийвчлан хэлбэл $w_i$ өргөнтэй хайрцаг $w_{i+1}$ дугаартай гишгүүрт огт хүрч чадахгүй юм.

Чамд Димагын шат болон унагах хайрцагны мэдээлэл дарааллаараа өгөгдсөн бол хайрцаг болгоны хувьд хайрцагын доод хэсэг хэр өндөрт хүрч тогтохыг тодорхойл. Өмнөх хайрцаг тогтсоны дараа л дараагын хайрцагыг унагаана.

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ ($1 ≤ n ≤ 10^5$) — шатны гишгүүрүүдийн тоо. Хоёр дахь мөрөнд үл буурах $n$ ширхэг элементтэй дараалал өгөгдөнө $a_1$, $a_2$, ..., $a_n$ ($1$ ≤ $a_i$ ≤ $10^9$; $a_i$ ≤ $a_{i+1}$). Дараагын мөрөнд нэг бүхэл тоо $m$ ($1$ ≤ $m$ ≤ $10^5$) - хайрцагны тоо. Дараагын $m$ ширхэг мөрөнд $w_i$, $h_i$ ($1$ ≤ $w_i$ ≤ $n$; $1$ ≤ $h_i$ ≤ $10^9$) - $i$-р хайрцагны хэмжээ.

Мөр бүрт тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

$m$ ширхэг тоог хэвлэ. Өгсөн дарааллын дагуу унагасан хайрцаг болгоны доод хэсэг ямар өндөрт газардаж байгааг хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: byambadorjp, Энхсанаа

Жишээ тэстүүд

Оролт
5
1 2 3 6 6
4
1 1
3 1
1 1
4 3
Гаралт
1
3
4
6
Оролт
3
1 2 3
2
1 1
3 1
Гаралт
1
3
Оролт
1
1
5
1 2
1 10
1 10
1 10
1 10
Гаралт
1
3
13
23
33

Тэмдэглэл

The first sample are shown on the picture.

Сэтгэгдлүүдийг ачааллаж байна...