Contest ôn tập THT bảng B - 2023 #03

Hôm nay shiba vừa mới nhận lương nên đã mời _minhduc đi ăn bữa tối, và tất nhiên shiba sẽ bao :Đ

Địa điểm shiba mời _minhduc đi ăn bữa tối hôm nay là cửa hàng LQDOJ, tất cả các món của cửa hàng này đều đồng giá \(C\) đô.

Nhân dịp cuối tuần cửa hàng có khuyến mãi cho khách hàng cứ mỗi lần đặt \(15\) món thì cửa hàng sẽ trả lại cho bạn \(S\) đô và tính số lượng để khuyến mãi về lại thành \(0\).

Tận dụng điều này _minhduc đã đặt \(N\) món để ăn no bụng, vì hiếm lắm anh ấy mới được shiba bao.

Yêu cầu: Bạn hãy tính số tiền shiba phải trả sau khi đã áp dụng khuyến mãi.

Input

• Chứa ba số nguyên dương lần lượt là \(N, C, S\) (\(1 \le N \le 10^9, 1 \le C \le 10^5, 1 \le S \le 1000\)), mỗi số cách nhau một khoảng trắng.

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Example

20 800 200

15800

30 400 1000

10000

cho hai dãy có cùng \(n\) số nguyên dương \(a_1,a_2,...,a_n\) và \(b_1,b_2,...,b_n\).

shiba muốn tạo ra một dãy cũng có \(n\) số nguyên dương \(c_1,c_2,...,c_n\) thỏa mãn rằng \(c_k\) \((1 \le k \le n)\) là giá trị lớn nhất của \(a_i \times b_j\) với mọi \(1 \le i \le j \le k\). Hay nói một cách khác, shiba cần tạo ra một dãy thỏa mãn rằng \(c_k = max(a_i \times b_j)\) với mọi \((1 \le i \le j \le k)\).

Yêu cầu: Bạn hãy giúp shiba tạo và in ra dãy \(c\) thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\).
• Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.
• Dòng cuối cùng chứa dãy \(b_1,b_2,...,b_n\) \((1 \le b_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) \((1 \le i \le n)\) in ra số \(c_i\) thỏa mãn điều kiện (\(i\) theo thứ tự tăng dần \(1,2,...,n\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(n \le 2 \times 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
3 2 20
1 4 1

3
12
20

Hôm nay là một ngày Chủ Nhật đẹp trời, shiba quyết định sẽ đi tập chạy quanh thành phố của mình để tăng cường sức khỏe sau \(7749\) ngày ngồi gõ code.

Thành phố nơi Thanh Nguyên sống có \(n\) cửa hàng bán đồ gia dụng, được đánh số từ \(1\) tới \(n\). shiba quyết định sẽ chạy bộ từ cửa hàng thứ \(1\) tới cửa hàng thứ \(n\) và sẽ mua các vật phẩm trong các cửa hàng. Cửa hàng thứ \(i\) có bán loại vật phẩm thứ \(a_{i}\) với giá tiền \(c_{i}\) (các cửa hàng khác nhau có thể bán cùng một loại vật phẩm). Trên đường chạy của mình, shiba cần mua \(m\) vật phẩm. Tại mỗi cửa hàng, cậu ấy quyết định sẽ mua vật phẩm đó hay không, nếu không thì cậu ấy sẽ bỏ qua cửa hàng đó và không thể mua vật phẩm ở cửa hàng đó nữa.

Hỏi số tiền ít nhất mà shiba cần chi để mua đủ các vật phẩm theo yêu cầu là bao nhiêu?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n,m \le 10^6, m \le n\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a_{i}\) và \(c_{i}\) (\(a_{i} \le n, c_{i} \le 10^9\)).
• Dòng thứ \(n+1\) chứa \(m\) số nguyên, là các vật phẩm cần mua. Các số có thể trùng nhau.

Output

• In ra một số nguyên duy nhất là số tiền ít nhất shiba phải chi. Nếu không mua được theo yêu cầu thì ghi ra số nguyên -1.

Example

6 4
1 2
1 3
1 4
1 5
2 2
2 3
1 1 2 1

11

Cho một xâu \(S\) chỉ chứa hai kí tự a và b. Bạn có thể thực hiện các thao tác sau nhiều lần tùy ý hoặc không cần thao tác:

• Chọn một lần chuỗi con aa ở vị trí bất kì mà nó xuất hiện trong xâu \(S\) và thay nó bằng b.
• Chọn một lần chuỗi con bb ở vị trí bất kì mà nó xuất hiện trong xâu \(S\) và thay nó bằng a.

Yêu cầu: Bạn hãy đếm xem có bao nhiêu xâu con khác nhau có thể tạo ra với các thao tác trên.

Input

• Chứa một xâu \(S\) duy nhất (độ dài của xâu \(S\) không quá \(2 \times 10^7\)).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Độ dài của xâu không quá \(10^5\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

aaaa

6

aabb

5

ababababa

1

babbabaaba

35