Problem B: 大小PIPI II

Problem B: 大小PIPI II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 306  Solved: 102
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI国有两种人,一种叫小PIPI,一种叫大PIPI。现在PIPI国想建设工厂,每个工厂都需要一定数量的大PIPI和一定数量的小PIPI,每个工厂都会用一个字符串表示所需要的大PIPI和小PIPI(字符串中大PIPI用P表示,小PIPI用p表示)。现在一共有n个大PIPI以及m个小PIPI ,请问PIPI国最多能够建设多少个工厂? 每个大PIPI和每个小PIPI都只能去一个工厂。

Input

第一行输入三个数字 n , m , t ,分别代表 大PIPI数量,小PIPI数量和待建设的工厂数量 (1<=n,m,t<=500)。
接下来每行一个字符串代表每个工厂所需的大PIPI和小PIPI, 每个字符串长度不超过1000。

Output

输出一行,代表PIPI国最多能够建设多少个工厂。

Sample Input

3 5 5
Pp
pppP
PPPppP
P
p

Sample Output

4

HINT

除了第三个工厂不能建设,其余的都可以建设起来。