In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
This time Byteland has a rectangular shape meters wide and meters high. Byteasar is a farmer and has his own field, which consists of unitary squares. Moreover, the common part of every horizontal layer of unitary squares and the Byteasar's field is connected (although the whole field may not be connected).
The king of Byteland gave a decree, which obliged every farmer to give a rectangular shape area meters wide and meters high (positioned horizontally or vertically), consisting of unitary squares, into king's possession. The position of this rectangle will be chosen by the king. Byteasar hopes, that there are a lot of possible positions of such rectangle, so the greedy king will not be able to make his decision fast. Help Byteasar and find the number of possible positions of the area (that lies inside Byteasar's field), that Byteasar can lose.
Write a program which:
The first line of the standard input contains four integers , , and (). The numbers denote respectively: dimensions of the Byteasar's field and dimensions of the area that must be given to the king. In the following lines there are descriptions of the consecutive horizontal layers of farmer's field. Each description consists of two integers and (, , ) - the fragment of the field in this layer begins meters from the left border of Byteland and consists of unitary squares.
One integer is to be written to the standard output. This integer should be the number of possible positions of the meters wide and meters high rectangular area inside Byteasar's field.
For the input data:
5 6 2 3 1 5 1 3 1 2 1 1 3 3 2 4
the correct result is:
This figure depicts the field from the sample input (dark color represents area belonging to the field).
We encourage C++ programmers to use STL data structures cautiously due to the data size. Improper usage may cause in exceeding time or memory limit.
Task author: Jakub Radoszewski.