NITT4 - Tiles

no tags 

Given a N x M floor with few blocks already filled, check if it is possible to fill the remaining space with only 2 x 1 blocks, if it is not possible, print the minimum number of 1 x 1 blocks required to fill the floor completely.

Input

First line contains N (number of rows), M (number of columns), B (number of already blocked cells), followed by B lines each containing 2 integers x, y coordinates of the blocked cell

1 <= N <= 100, 1 <= M <= 100, 0 <= B <= N*M

Output

If it is possible to fill the floor with only 2 x 1 tiles, print Yes, else print No and the minimum number of 1 x 1 tiles required.

Example

Input:
1 1 0
Output:
No 1
Input:
2 2 0
Output:
Yes
Input:
2 2 2
0 1
1 0
Output:
No 2

hide comments
Mitch Schwartz: 2013-11-16 05:32:30

@Jacob Plachta: Thanks for clarifying!

Jacob Plachta: 2013-11-12 17:03:06

1. The coordinates of the blocked cells are given as (row, column).
2. For "No", the outputted value is the minimum number of 1x1 tiles which must be added so that the remaining tiles can be filled with 1x2 tiles.

Zhouxing Shi: 2013-05-06 06:47:41

【【orz @nblt & @dhy007!!!!!!!!】】


@nblt : should be "dhy" not dyh

Last edit: 2013-05-16 04:14:18
nblt: 2013-05-06 06:13:10

Orz dyh!!

Mitch Schwartz: 2012-12-06 04:28:10

I think it's not clear whether we must print (1) number of 1x1 blocks required in order to make the floor tileable by 1x2 blocks (2) number of 1x1 blocks required simply to fill the floor. Problem is worded implying (2), but since it's a trivial calculation (once we have decided "No"), maybe (1) is desired.

Ricardo Oliveira [UFPR]: 2012-11-18 14:32:31

yes

NiNjA: 2012-11-01 14:56:34

Can 2X1 tiles be placed like 1X2 tiles, horizontally ?


Added by:jack(chakradarraju)
Date:2012-09-30
Time limit:0.210s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET