Ôn tập THT bảng B (contest ôn HSG 9-10 #9)

Quỳnh muốn mua trà sữa mời các bạn. Cửa hàng đang có chương trình khuyến mãi đặc biệt: Giá niêm yết mỗi ly là \(A\) đồng. Tuy nhiên, nếu khách hàng mua số lượng từ \(K\) ly trở lên, cửa hàng sẽ tính giá ưu đãi chỉ còn \(B\) đồng cho mỗi ly (biết \(B < A\)).

Yêu cầu: Cho biết số lượng ly trà sữa \(N\) mà Quỳnh muốn mua, hãy tính tổng số tiền Quý phải trả.

Input

Đọc vào từ tệp văn bản TRASUA.INP:

• Dòng duy nhất chứa 4 số nguyên dương \(N, K, A, B\) (\(1 \le N,K \le 1000\); \(1 \le B < A \le 10^5\)).

Output

Ghi ra tệp văn bản TRASUA.OUT:

• Ghi một số nguyên duy nhất là tổng số tiền phải trả.

Example

2 5 30 20

60

10 5 30 20

200

Quý là một người yêu thích số học. Cậu định nghĩa: Một số nguyên dương \(M\) được gọi là số nguồn của \(N\) nếu thỏa mãn phương trình:

Trong đó \(S(M)\) là tổng các chữ số của \(M\). Ví dụ: \(M = 12\) là số nguồn của \(N = 15\) vì \(12 + (1 + 2) = 15\).

Yêu cầu: Cho số nguyên dương \(N\). Hãy tìm số nguồn \(M\) nhỏ nhất của \(N\). Nếu không tồn tại số nguồn nào, in ra -1.

Input

Đọc vào từ tệp văn bản SOURCE.INP:

• Dòng duy nhất chứa số nguyên dương \(N\).

Output

Ghi ra tệp văn bản SOURCE.OUT:

• Ghi ra số nguồn nhỏ nhất tìm được, hoặc -1 nếu không tồn tại.

Example

15

12

20

-1

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N \leq 10^4\)
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 2\cdot 10^9\)

Linh là một bartender chuyên nghiệp tại tiệm nước Hi4. Với content pha trà sữa ASMR siêu bánh cuốn trên TokTik, Linh đã thu hút lượng lớn người hâm mộ. Để chuẩn bị cho đợt khách đổ bộ sắp tới, tiệm vừa sắm một robot rót nguyên liệu tự động. Khi hoạt động, robot này sẽ phun ra một dải gồm \(N\) đơn vị nguyên liệu liên tiếp trên băng tải. Mỗi đơn vị (tương đương một muỗng) được ký hiệu là 1 nếu đó là đường và 0 nếu đó là trà.

Để pha được một bình trà sữa "khổng lồ" mà vẫn giữ được vị ngon khét tiếng, Linh cần chọn ra một đoạn liên tiếp dài nhất trên băng tải sao cho các muỗng nguyên liệu trong đoạn đó đảm bảo đúng tỉ lệ: Số lượng muỗng trà (0) phải gấp đúng \(K\) lần số lượng muỗng đường (1).

Yêu cầu: Tìm độ dài của đoạn con liên tiếp dài nhất thỏa mãn tỉ lệ trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \leq N \leq 10^5; 1 \leq K \leq 100\))
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(A_i \in \{0, 1\}\))

Output

• Một số nguyên duy nhất là độ dài đoạn con lớn nhất thỏa mãn tỉ lệ yêu cầu. Nếu không có đoạn nào thỏa mãn, in 0

Example

7 2
0 1 0 0 1 0 0

6

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 200\)
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5000\)
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm

Lương đang ngồi trong Hi4, uống trà sữa của Linh pha nhưng không thảo luận về công nghệ lõi Xati với đệ ruột của anh ấy, mà lại bấm điện thoại chơi Free Fire. Trong ván game đặc biệt này, anh ấy cần nhảy dù xuống một cánh đồng kích thước \(N \times M\) được chia thành lưới ô vuông (gồm \(N\) dòng và \(M\) cột). Tại mỗi ô \((i, j)\) luôn có gió thổi cố định theo một trong 4 hướng: Đông (R), Tây (L), Nam (D), Bắc (U).

Khi Lương đáp xuống một ô, gió sẽ lập tức thổi cậu bay sang ô kế tiếp theo hướng gió. Quá trình này lặp lại cho đến khi cậu bay ra khỏi cánh đồng hoặc bị kẹt trong một vòng lặp gió xoáy.

Tuy nhiên, tại vị trí đích \((X, Y)\) có một cổng dịch chuyển. Nếu Lương được gió thổi đến ô này (hoặc đáp dù trúng ô này), cậu sẽ lập tức được dịch chuyển an toàn đến khu vực loot đồ mà không bị gió thổi đi tiếp.

Yêu cầu: Đếm xem có bao nhiêu ô xuất phát (bao gồm cả ô \((X, Y)\)) mà từ đó Lương sẽ đến được cổng dịch chuyển tại \((X, Y)\).

Input

• Dòng đầu chứa 4 số \(N, M, X, Y\) (\(1 \le X \le N; 1 \le Y \le M\))
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) ký tự thuộc tập \(\{\texttt{U}, \texttt{D}, \texttt{L}, \texttt{R}\}\) mô tả hướng gió

Output

• Một số nguyên duy nhất là số lượng ô xuất phát thỏa mãn

Example

3 3 2 2
RDL
RUL
URU

9

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, M \le 50\)
• Subtask \(2\) (\(50\%\) số điểm): \(N, M \le 2000\)