Submit | All submissions | Best solutions | Back to list |
VBLOCKS - Blocks |
English | Vietnamese |
Bom and Cuoi are playing a puzzle game together. The game consists of a horizontal board of L unit cells (size 1x1) and some horizontal segments of size 1xS (made from S unit cubes). Bom has to put these segments on the board so that two consecutive segments have to be at least D cells apart from each other (i.e. there are at lease D empty cells between them).
To make the game more difficult, Cuoi gives Bom some more conditions. Each condition has the form: "the ith cell must be covered" or "the ith cell must not be covered" (by a cube).
Help Bom to find a way to put the segments so that Cuoi's conditions are satisfied. If one way exists, determine the maximum number of segments that Bom can use.
Input
- The first line contains three integers L, S, D (1 ≤ L ≤ 100000).
- The second line contains an integer K that is the number of Cuoi's conditions.
- Each line in the next K lines contains two integers i and d (d=1 or d=2) representing a Cuoi's condition: d=1 means "the ith cell must be covered" and d=2 means "the ith cell must not be covered". The values of i are in ascending order.
Output
If there is no way for Bom to put the segments satisfying Cuoi's conditions, print -1. Otherwise, print the maximum number of segments that Bom can use.
Constraint
There are 50% of the test cases corresponding to 50% of the grades in which 1 ≤ L ≤ 1000.
Example
Input 10 4 2 2 2 1 5 2 Output 2 Input 4 2 1 2 1 1 3 1 Output -1
Added by: | Jimmy |
Date: | 2008-06-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |
Resource: | VNOI Marathon '08 - Round 5/DivA Problem Setter: Ngô Minh Đức |