Ամրոց
Մրցույթն առանց գրաֆների ու ծառերի մրցույթ չէ
Երիտասարդ գրաֆը ցանկանում էր ամրոց ունենալ։ Գրաֆի տրամադրության տակ է գտնվում մի անտառածածկ ուղանկյունաձև տարածք։ Գրաֆը սիրում է բնությունը և ուզում է ինչքան հնարավոր է քիչ ծառեր կտրել։ Ամրոցը նույնպես պետք է զբաղեցնի ուղանկյունաձև տարածք։ Անտառը կարել է ներկայացնել երկու չափանի զանգվածի տեսքով որտեղ կան երկու տեսակի վանդակներ՝ ծառ և դատարկ։ Ամրոցը նույնպես կարել է ներկայացնել երկու չափանի զանգվածի տեսքով որտեղ կան երկու տեսակի վանդակներ՝ քար և դատարկ։ Ամրոցը կարել է պտտեցնել և հայելային արտապատկերել։ Ամրոցը պետք է տեղադրել այնպես, որ այն ամբողջությամբ գտնվի անտառի մեջ (նույնիսկ եթե եզրերը դատարկ են)։ Երաշխավորվում է որ պատասխան գոյություն ունի։
Մուտքային տվյալներ
Առաջին տողում տրված են երկու
n, m թվեր՝ անտառի տողերի և սյուների քանակները։ Հաջորդ n տողերում նկարագրված է անտառը .-ը նշանակում է բաց տեղ, #-ը ծառ։ Հաջորդ տողում տողում տրված են երկու n1, m1 թվեր՝ ամրոցի տողերի և սյուներ քանակները։ Հաջորդ n1 տողերում նկարագրված է ամրոցը .-ը նշանակում է դատարկ #-ը պատ։Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ՝ մինիմալ ծառերի քանակը, որ գրաֆը ստիպված կլինի հատել։
Սահմանափակումներ
Subtask-1: n, m, n1, m1 ≤ 100։
Subtask-2: n, m, n1, m1 ≤ 300։
Օրինակներ
Մուտք
5 5
####.
####.
####.
####.
.....
5 5
#....
#....
#....
#....
#####
Ելք
0
Մուտք
10 20
#.###.#.###.########
#.###........###.###
.##.#........##.#.##
#.#####..##..###.###
#.###..#.#.#.#.#..##
#.#.#.#...##..######
#####...#.....#.#.##
#.###.#..#....##.###
#.#.###.#.#.####.##.
#####.#.###.###.##..
8 8
###..###
########
###..###
.#....#.
.#....#.
###..###
########
###..###
Ելք
10Աղբյուրը. Դպրոցական 2021
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB