Cho hai số nguyên dương $x,k$.

Tìm số nguyên dương bé nhất sao cho $x\times y$ chia hết cho $k$.

Dữ liệu vào

Gồm một dòng duy nhất chứa hai số nguyên $x,k$ cách nhau bởi dấu cách ($x,k\le {10}^{18}$).

Kết quả

Gồm một số nguyên dương duy nhất là đáp án của đề bài.

Ví dụ

MINDIV.INP

8 6

MINDIV.OUT

3

MINDIV.INP

12 7

MINDIV.OUT

7

Ràng buộc

• Có 50% số lượng test ứng với $x,k\le {10}^6$.
• Có 50% số lượng test ứng với $x,k\le {10}^{18}$.

Trong kỳ nghỉ hè, Hiển và Hạo đang miệt mài ôn thi vòng 2 đội tuyển HSG Tin học. Một buổi chiều, Hạo đưa ra một bài toán thú vị: Cho một dãy số nguyên $A$ gồm $n$ phần tử $A_1,A_2,\dots ,A_n$. Hãy tìm dãy con liên tiếp có tổng lớn nhất. Hiển nhanh chóng nhận ra đây là bài toán kinh điển và quyết định viết chương trình giải nhanh gọn. Hãy giúp Hiển nhé!

Dãy con liên tiếp của $A$ là một đoạn liên tục gồm các phần tử nằm liền nhau của $A$. Ví dụ, với $A=[6,-1,2,8,-4]$, dãy $[-1,2,8]$ là một dãy con liên tiếp, còn $[6,2,-4]$ thì không.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ ($1\le n\le {10}^5$) — độ dài dãy $A$.
• Dòng thứ hai gồm $n$ số nguyên $A_i$ ($|A_i|\le {10}^9$) mô tả dãy $A$.

Kết quả

Gồm một dòng duy nhất chứa giá trị tổng lớn nhất của dãy con liên tiếp tìm được.

Ví dụ

MAX.INP

6
-1 3 -1 2 1 -5

MAX.OUT

5

Giải thích: Dãy con liên tiếp có tổng lớn nhất là $A_2+A_3+A_4+A_5=3+(-1)+2+1=5$.

Ràng buộc

• Có 50% số test ứng với $n\le {10}^3$, $|A_i|\le {10}^4$.
• Có 50% số test còn lại ứng với $n\le {10}^5$, $|A_i|\le {10}^9$.

Trong một ngôi nhà lớn có $n$ căn hộ được xếp thành một hàng từ trái sang phải, mỗi căn hộ chứa chính xác một Pokémon thuộc một loại nào đó (được biểu diễn bằng một chữ cái in hoa hoặc in thường trong bảng chữ cái tiếng Anh).

Bạn Nhi, một nhà huấn luyện Pokémon trẻ tuổi, muốn thu thập tất cả các loại Pokémon xuất hiện trong ngôi nhà này. Nhi có thể vào từ đường phố tại một căn hộ bất kỳ, đi qua một số căn hộ khác (mỗi căn hộ tối đa một lần) và sau đó ra khỏi nhà tại một căn hộ bất kỳ. Các căn hộ được kết nối với nhau: căn hộ $i$ kết nối với căn hộ $i-1$ và $i+1$ (với $1<i<n$), căn hộ $1$ chỉ kết nối với căn hộ $2$, căn hộ $n$ chỉ kết nối với căn hộ $n-1$.

Hãy tìm số lượng căn hộ ít nhất mà Nhi cần ghé thăm để có thể thu được tất cả các loại Pokémon có mặt trong ngôi nhà.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ ($1\le n\le {10}^5$) — số căn hộ.
• Dòng thứ hai chứa xâu $s$ có độ dài $n$, chỉ gồm các chữ cái Latinh in hoa và in thường. Ký tự thứ $i$ cho biết loại Pokémon trong căn hộ thứ $i$.

Kết quả

In ra một số nguyên duy nhất — số căn hộ tối thiểu Nhi cần ghé thăm.

Ví dụ

EVERYWHERE.INP

3
AaA

EVERYWHERE.OUT

2

EVERYWHERE.INP

7
bcAAcbc

EVERYWHERE.OUT

3

EVERYWHERE.INP

6
aaBCCe

EVERYWHERE.OUT

5

Ràng buộc

• Có 50% số lượng test ứng với $n\le 1000$.
• Có 50% số lượng test ứng với $n\le {10}^5$.

Khôi tổ chức một bữa tiệc sinh nhật kỳ lạ. Cậu ấy mời $n$ người bạn và gán cho người bạn thứ $i$ một số nguyên $k_i$.
Bây giờ Khôi muốn tặng mỗi người một món quà.
Trong cửa hàng gần đó có $m$ món quà khác nhau, món quà thứ $j$ có giá $c_j$ đồng $(1\le c_1\le c_2\le \dots \le c_m)$.
Không được phép mua một món quà nhiều hơn một lần.

Với người bạn thứ $i$, Khôi có thể:

• Mua cho họ một món quà $j\le k_i$ với giá $c_j$ đồng, hoặc
• Đưa trực tiếp cho họ $c_{k_i}$ đồng.

Hãy giúp Khôi xác định tổng chi phí nhỏ nhất để tổ chức bữa tiệc.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $t$ $(1\le t\le 10)$ — số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $n,m$ $(1\le n,m\le {10}^4)$ — số lượng bạn bè và số lượng món quà.
• Dòng tiếp theo chứa $n$ số nguyên $k_1,k_2,\dots ,k_n$ $(1\le k_i\le m)$.
• Dòng tiếp theo chứa $m$ số nguyên $c_1,c_2,\dots ,c_m$ $(1\le c_1\le c_2\le \dots \le c_m\le {10}^9)$.

Kết quả

Với mỗi bộ test, in ra một số nguyên duy nhất — chi phí nhỏ nhất.

Ví dụ

BIRTHDAY.INP

2
5 4
2 3 4 3 2
3 5 12 20
5 5
5 4 3 2 1
10 40 90 160 250

BIRTHDAY.OUT

30
190

Ràng buộc

• Có 50% số lượng test ứng với $n,m\le {10}^3$.
• Có 50% số lượng test ứng với $n,m\le {10}^4$.