Diferențe pentru problema/capsuni între reviziile #5 si #7

== include(page="template/taskheader" task_id="capsuni") ==

_Notă: valorile maxime pentru N și M au fost modificate de la 100000 la 500000 pentru a corespunde testelor originale. De asemenea limita de timp de executare a fost micșorată de la 3 secunde la o secundă._
 

Vali iubește torturile de ciocolată, de vanilie, însă nu le suportă pe cele de căpșuni. Acesta este alergic la căpșuni. Nu vreți să știți ce pățește Vali când mănâncă o căpșună. Nimeni nu vrea să știe.
Vali a primit de la dușmanul său Leinad cadou un tort dreptunghiular împărțit în N linii și M coloane ce conține în unele zone CĂPȘUNI. Vali dorește să mănânce tort folosindu-se de următorul algoritm: Cât timp există o linie pe care nu se află căpșuni, acesta taie felia formată din linia respectivă, o mănâncă și merge mai departe. Când nu mai există nicio linie care să nu conțină vreo căpșună, caută o coloană pe care nu se află nicio căpșună și mănâncă toate celulele rămase conținute în acea coloană, apoi caută altă coloană. Când nu mai există nicio coloană care să nu conțină căpșuni, atunci Vali îi trimite mesaj dușmanului său Leinad cu numărul de celule din tort pe care le-a mâncat.

h2. Restricții

* $1 ≤ N, M ≤ 100.000$

* $1 ≤ N, M ≤ 500.000$

* $0 ≤ K ≤ 1.000.000$
* $1 ≤ x ≤ N$
* $1 ≤ y ≤ M$