Անձրև
Անապատային տեղանքը ներկայացված է N x M չափի վանդակավոր ցանցի տեսքով։ Որոշ վանդակներում կան այգիներ, մյուսներն ազատ են։ Կից (ընդհանուր կողմ ունեցող) ալգիներն ունեն ընդհանուր ոռոգման համակարգ, այնպես, որ եթե նրանցից մեկում ջուր հայտնվի, ապա այն կփոխանցվի մյուսին։ Այսինքն, այգիները կազմում են կապակցված կտորներ։
Արեգը ղեկավարում է արհեստական ամպը, որը H x W ուղղանկյունաձև տեսք ունի։ Նա ցանկանում է ամպը տեղաշարժել և տեղադրել տեղանքի վերևում այնպես, որ նրա կողմերը զուգահեռ լինեն տեղանքի կողմերին և անձրև առաջացնել։ Արեգը ցանկանում է ամպը տեղադրել այնպես, որ որքան հնարավոր է շատ կապակցված կտորներ ջուր ստանան, այսինքն նա ցանկանում է մաքսիմիզացնել ոչ թե վանդակների քանակը, այլ կոմպոնենտների քանակը։ Ջուր ստանալու համար պարտադիր չէ, որ ամբողջ կոմպոնենտն ամպի տակ լինի, բավական է, որ նրա վանդակներից մեկն ամպի տակ լինի։
Օգնեք Արեգին պարզելու, թե առավելագույնը այգիների քանի կապակցված կոմպոնենտ է հնարավոր ջրել։
Մուտքային տվյալներ
Առաջին տողում տրված են 𝑁, 𝑀 (1 ≤ 𝑁,𝑀 ≤ 3000), 𝐻 (1 ≤ 𝑊 ≤ 𝑁) և 𝑊(1 ≤ 𝐻 ≤ 𝑀) ամբողջ թվերը՝ աղյուսակի չափերը և ամպի չափերը: Հաջորդ 𝑁 տողերից յուրաքանչյուրում տրված են 𝑀 սիմվոլներ, որոնք իրարից առանձնացված են մեկ բացատանիշով, նրանցից յուրաքանչյուրը նկարագրում է մեկ վանդակ՝ «x» (փոքր լատինատառ x), եթե այնտեղ այգիներ կան, և «.», եթե այգիներ չկան:
Ելքային տվյալներ
Ստանդարտ ելքի միակ տողում տպեք խնդրի պատասխանը:
Օրինակ
Մուտք | Ելք |
10 12 4 5
. x x . . x . . x x x .
. x . . x x . . . x x x
x x x . . x x x x . . .
. . x x . . . . . . x x
x . . x x x x . . . x x
x x . x . . x x . x x .
. x . . x x . x x . x .
. . x . . x x . . x x .
x x x . . . x x x x .
. . x . . x x . . . x . x | 4 |
Բացատրություն
Ամպի վերևի ձախ անկյունը կարելի է տեղադրել, օրինակ, 5-րդ շարքի 1-ին սյունակում:
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (8 միավոր)
- Ենթախնդիր 2 (10 միավոր)
- Ենթախնդիր 3 (9 միավոր), բոլոր կոմպոնենտները բաղկացած են մեկ վանդակից,
- Ենթախնդիր 4 (11 միավոր), կոմպոնենտների առավելագույն քանակը 20 է,
- Ենթախնդիր 5 (11 միավոր), կոմպոնենտների առավելագույն քանակը 400 է,
- Ենթախնդիր 6 (14 միավոր), յուրաքանչյուր կոմպոնենտ բաղկացած է առավելագույնը 20 վանդակից,
- Ենթախնդիր 7 (37 միավոր)Լրացուցիչ սահմանափակումներ չկան:
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB