Задача №112600. Не перегораживайте Нил
НЛО приземлилось в районе реки, ее вид заворожил инопланетян, потому что на их планете вообще нет рек. Сейчас они хотят построить свой инопланетный поселок на одной из земных рек, но также они знают, что на Земле очень хрупкая экосистема, поэтому нельзя перегораживать реку очень сильно. Но инопланетяне абсолютно не знают, как устроены реки, поэтому они обратились к вам с просьбой написать программу, которая вычислит максимальную пропускную способность реки, после постройки их инопланетного поселка.
Инопланетяне предпочитают строить здания на тех реках, берега которых представляют из себя параллельные прямые, поэтому область реки, где будут строить инопланетяне, можно себе представить как прямоугольную таблицу W × H , у которой каждая клеточка имеет координаты ( X , Y ). Каждая клеточка пропускает через себя 1 кубический метр воды в секунду, и вода может перетекать только между клеточками соседним по стороне. Каждая клеточка на южной стороне реки ( Y = 0 ) имеет приток воды из реки в размере 1 кубический метр воды в секунду. Каждый дом в поселке занимает прямоугольник, состоящий из единичных клеточек; если в клеточке стоит дом, то вода через нее протекать не может. Ваша задача — вычислить, сколько кубических метров за секунду пропускает поселок инопланетян. То есть сколько кубических метров воды вытекает из всех северных клеток поселка ( Y = H - 1 ) в сумме.
Как известно, вода несжимаема, то есть не может накапливаться в клетке, соответственно если в клетку втекло сколько-то воды, то столько же должно и вытечь.
В первой строке содержатся два целых числа W и H — ширина и высота реки соответственно (\(3\leq W \leq 1000;\; 3\leq H \leq 10^{8})\). В следующей строке находится число B — количество домов в поселке инопланетян (\(0 \leq B \leq 1000\)).
Следующие B строк содержат четыре целых координаты X 0 , Y 0 , X 1 , Y 1 . Где X 0 и Y 0 — координаты нижней левой клеточки дома, а X 1 и Y 1 — координаты верхней правой клеточки дома ( 0 ≤ X 0 ≤ X 1 < W и 0 ≤ Y 0 ≤ Y 1 < H ). Домики не перекрываются, но могут касаться по стороне или ребрам.
Выведите одно число — максимальную пропускную способность поселка в кубических метрах в секунду.
3 3 2 2 0 2 0 0 2 0 2
1
5 6 4 1 0 1 0 3 1 3 3 0 2 1 3 1 5 2 5
2