D. Меншиков, Услада, Хорас ба шоон хананууд

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

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

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

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

Санкт-Петербургийн амьтны хүрээлэнгийн Меншиков, Услада хоёр баавгай, Киев хотын амьтны хүрээлэнгийн Хорас заан гурав хаа нэгтээгээс маш олон модон шоо олсон байна. Тэд бусад дээр нь нэг шоо тавих замаар шоонуудаар цамхаг хийж эхэлжээ. Тэд олон цамхагыг хана шиг дараалан байрлуулж тодорхойлсон байна. Хана нь ялгаатай өндөртэй цамхагуудаас бүрдэнэ.

Хорас эхлээд ханаа хийж дууссан байна. Тэр энэ ханаа заан гэж нэрлэсэн ба хана нь $w$ цамхагуудаас бүрдэнэ. Баавгайнууд ч бас хана хийж дууссан боловч тэд түүнд нэр өгч чадахгүй байна. Тэдний хана $n$ цамхагаас бүрдэнэ. Хорас баавгайнуудын цамхаг руу хараад бодов: хананы хэдэн хэсгүүд нь "заан шиг харагдаж" чадаж байна? Хэрвээ цамхагуудын $w$ үргэлжилсэн хэсгийн өндрүүд Хорасын хананы цамхагуудын өндрүүдийн дараалалтай тохирч байвал тэр "заан шиг харагдаж" чадна. Аль болох олон заан харахын тулд, Хорас баавгайнуудын ханыг өргөх эсвэл буулгах боломжтой. Тэр ч бүү хэл газрын түвшнээс доош ханыг (тодруулга авахыг хүсвэл жишээний зургийг үзнэ үү) буулгаж болно.

Таны даалгавар бол Хорасд "заан шиг харагдаж" чадаж байгаа хэсгүүдийн тоог тоолох юм.

Оролт

Эхний мөр нь хоёр бүхэл $n$, $w$ ($1 ≤ n, w ≤ 2*10^{5}$) тоонуудыг агуулна. Эдгээр нь харгалзан баавгайнуудын цамхагуудын тоо болон зааны хананы цамхагуудын тоо. Хоёр дахь мөр нь $n$ ширхэг $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$) бүхэл тоонуудыг агуулах ба эдгээр нь баавгайнуудын хананы цамхагуудын өндрүүд юм. Гурав дахь мөр нь $w$ ширхэг $b_{i}$ ($1 ≤ b_{i} ≤ 10^{9}$) бүхэл тоонуудыг агуулна. Эдгээр нь зааны хананы цамхагуудын өндрүүд.

Гаралт

Хорасд "заан шиг харагдаж" чадаж байгаа баавгайнуудын хананы хэсгүүдийн тоог хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
13 5
2 4 5 5 4 3 2 2 2 3 3 2 1
3 4 4 3 2
Гаралт
2

Тэмдэглэл

Жишээн дээрх зүүн талын зураг нь Хорасын хана, баруун талын зураг нь баавгайнуудын хана. Хорасд "заан шиг харагдаж" чадаж байгаа хэсгүүд нь саарал өнгөтэй байна.

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