G. Turning Red
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
8 6
GBRBRRRG
2 1 4
1 2
4 4 5 6 7
3 5 6 7
1 8
1 8
Output
8
Input
4 3
RGBR
2 1 2
2 2 3
2 3 4
Output
impossible
Input
4 4
GBRG
2 1 2
2 2 3
2 3 4
1 4
Output
6
Input
3 3
RGB
1 1
1 2
1 3
Output
3