Cho ~2~ mảng số nguyên ~a_1, a_2, . . . , a_n~ và ~b_1, b_2, . . . , b_m~. Mảng ~c~ được xây dựng bằng cách lấy tất cả tích ~a_i \times b_j~ của mọi cặp ~(i, j), 1 ≤ i ≤ n, 1 ≤ j ≤ m~. Tìm số bé thứ ~k~ trong dãy ~c~ (số bé nhất được hiểu là số bé thứ ~1~)

Input

• Dòng đầu chứa số ~k~ ~(1 ≤ k ≤ n × m)~
• Dòng thứ ~2~ chứa số ~n~ và ~n~ số nguyên ~a_1, a_2, . . . , a_n~
• Dòng cuối cùng chứa số ~m~ và ~m~ số nguyên ~b_1, b_2, . . . , b_m~

Output

• Một số nguyên duy nhất là kết quả bài toán

Subtask

• Subtask ~1~ (~30\%~ số điểm): ~n,m \le 2000~
• Subtask ~2~ (~30\%~ số điểm): ~a_i, b_i > 0~
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

6
3 1 2 3
2 0 -1

Sample Output 1

0

Khu vực bạn đang sống có ~n~ thành phố và chúng được nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối giữa ~2~ thành phố ~u_i~ và ~v_i~ và bạn cần thời gian ~t_i~ để đi hết con đường thứ ~i~.

Là một đặc vụ ngầm mới gia nhập tổ chức, bạn cải trang thành một shipper. Trong ~q~ ngày tiếp theo, ngoài các đơn hàng bình thường ra, mỗi ngày bạn cần phải vận chuyển một đơn hàng bí mật cho tổ chức. Ngày thứ ~i~ bạn cần vận chuyển đơn hàng bí mật này từ thành phố ~x_i~ đến thành phố ~y_i~.

Để thể hiện được là một đặc vụ chuyên nghiệp, bạn cần phải giao đơn hàng bí mật này trong thời gian ngắn nhất có thể. Trong ~q~ ngày tới, hãy tính xem ngày thứ ~i~ bạn cần mất bao nhiêu thời gian để hoàn thành nhiệm vụ.

Input

• Dòng đầu tiên gồm 3 số nguyên dương ~n~, ~m~ và ~q~.

• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm 3 số nguyên dương ~u_i~, ~v_i~ và ~t_i~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên dương ~x_i~ và ~y_i~.

Ràng buộc dữ liệu

• ~1 \leq n, q \leq 10^5~.

• ~n-1 \leq m \leq n+30~.

• ~1 \leq u_i, v_i, x_i, y_i \leq n~.

• ~1 \leq t_i \leq 2 \cdot 10^5~.

• Dữ liệu đảm bảo liên thông giữa ~n~ thành phố.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ chứa một số nguyên là thời gian giao hàng ngắn nhất trong ngày ~i~.

Scoring

Subtasks

Sample Input 1

5 6 3
1 2 5
1 3 2
2 3 1
2 4 8
3 4 9
4 5 2
1 5
5 2
3 5

Sample Output 1

13
10
11

Sample Input 2

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

Sample Output 2

7
7
8

Bạn vừa tốt nghiệp HUCE (Đại Học Xây Dựng Hà Nội), và vừa nhận được việc: xây một tuyến cáp treo cho vương quốc HNAms.

Quốc vương chỉ tay vào một vùng đồi núi, nơi có ~n~ ngọn núi thẳng hàng, được đánh số từ ~1~ tới ~n~. Ngọn núi thứ ~i~ có độ cao là ~a_i~, biết rằng ~a_i \le a_{i+1} (\forall 1 \le i \le n - 1)~.

Để làm một tuyến cáp treo từ ngón núi thứ ~i~ tới ngọn núi thứ ~j~, bạn cần bỏ chi phí là:

• ~min_{v\in Z} \sum_{s=i}^j |a_s - v|^k~, ở đây ~k~ là một hằng số được Quốc vương cho trước.

Tất nhiên, vì bạn là kĩ sư xuất sắc, Quốc vương sẽ giao cho bạn ~G~ nhóm thợ để thực hiện xong dự án. Nhiệm vụ của bạn là chia dãy ~n~ ngọn núi này ra thành ~G~ đoạn, sao cho mỗi ngọn núi nằm trong duy nhất một đoạn, và mỗi nhóm thợ sẽ phụ trách xây dựng một đoạn tương ứng.

nhiệm vụ của bạn là xác định cách phân chia công việc cho G đội thợ sao cho tổng chi phí xây dựng của họ được tối thiểu hóa.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~N, G, k (1 ≤ N ≤ 2000, 1 ≤ G ≤ N, 1 ≤ k ≤ 2)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N (1 ≤ a_i ≤ 10^6, a_i ≤ a_{i+1}~ với mọi ~1 \le i < N)~.

Subtask

• Subtask ~1~ ~(30\%)~ : ~n \le 200~.
• Subtask ~2~ ~(30\%)~ : ~n \le 2000, k = 1~.
• Subtask ~3~ ~(40\%)~ : Không ràng buộc gì thêm.

Output

• In ra một dòng chứa chi phí xây dựng tối thiểu cần thiết.

Sample Input 1

3 1 1
1 2 3

Sample Output 1

2

Sample Input 2

3 1 2
1 2 3

Sample Output 2

2

Sample Input 3

5 1 2
1 2 3 4 5

Sample Output 3

10

Trong tiết khoa học máy tính hôm nay, Tí đã học về cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm. Một cây tìm kiếm nhị phân gồm các giá trị ~w_{u}~ phân biệt có tính chất sau:

• Mỗi đỉnh có tối đa hai đỉnh con (trái và phải).
• Với mỗi đỉnh ~u~, các đỉnh ~v~ ở cây con bên trái đều có giá trị nhỏ hơn ~u~ (~w_{u} > w_{v}~).
• Với mỗi đỉnh ~u~, các đỉnh ~v~ ở cây con bên phải đều có giá trị lớn hơn ~u~ (~w_{u} < w_{v}~).

Nhận thấy đây là một cấu trúc dữ liệu thú vị và mới mẻ, Tí đã nghĩ ra một bài toán sau: Xét một cây nhị phân tìm kiếm gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~, đỉnh ~u~ có trọng số ~c_u~ và giá trị ~w_{u}~. Tại mỗi đỉnh ~u~, với đỉnh ~v~ (khác ~u~) là đỉnh thuộc cây con gốc ~u~, đặt ~s_{u} = c_{u} + \sum w_{v}~. Hãy tìm cây nhị phân tìm kiếm có ~\max(s_{1}, s_{2}, \ldots, s_{n})~ nhỏ nhất. Nếu có nhiều cây thỏa mãn, hãy tìm cây có thứ tự từ điển lớn nhất.

Cây ~A~ có thứ tự từ điển lớn hơn cây ~B~ nếu dãy tiền thứ tự của cây ~A~ có thứ tự từ điển lớn hơn cây ~B~.

Dãy tiền thứ tự của một cây có thể thu được bằng cách duyệt các đỉnh theo thứ tự như sau: duyệt đỉnh gốc đầu tiên, sau đó duyệt cây con bên trái và cuối cùng là cây con bên phải.

Dãy ~a~ có thứ tự từ điển lớn hơn dãy ~b~ nếu tồn tại vị trí ~i~ sao cho ~a_{j} = b_{j}~ với mọi ~1 \leq j < i~ và ~a_{i} > b_{i}~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^{5}~) là số lượng đỉnh của cây tìm kiếm nhị phân.
• Dòng tiếp theo chứa ~n~ số nguyên ~c_{1}, c_{2}, \ldots, c_{n}~ (~1 \leq c_{i} \leq 10^{9}~).
• Dòng tiếp theo chứa ~n~ số nguyên ~w_{1}, w_{2}, \ldots, w_{n}~ (~1 \leq w_{1} < w_{2} < \ldots < w_{n} \leq 10^{9}~).

Output

• Dòng đầu tiên chứa một số nguyên là ~\max(s_{1}, s_{2}, \ldots, s_{n})~ trong cây tìm kiếm nhị phân tìm được.
• Dòng tiếp theo chứa ~n~ số nguyên là dãy tiền thứ tự của cây.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \leq 20~.
• Subtask ~2~ (~20\%~ số điểm): ~n \leq 4 \times 10^{2}~.
• Subtask ~3~ (~20\%~ số điểm): ~n \leq 3 \times 10^{3}~.
• Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4
4 3 2 1
1 2 3 4

Sample Output 1

7
4 3 2 1

Sample Input 2

6
27 10 44 32 15 41
2 3 4 5 6 7

Sample Output 2

44
5 4 2 1 3 6