Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VBLOCKS - Blocks

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

Được gửi lên bởi:Jimmy
Ngày:2008-06-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:VNOI Marathon '08 - Round 5/DivA
Problem Setter: Ngô Minh Đức

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.