Bài 1. Trồng cây

Để làm cho thành phố xanh hơn và đẹp hơn, bác thị trưởng cho trồng cây dọc theo một con đường lớn. Con đường dài x km. Cứ mỗi 10 m thì trồng 1 cây.

Biết rằng không trồng cây ở vị trí 0 m, nghĩa là không trồng cây ngay tại đầu con đường. Cây đầu tiên sẽ được trồng ở vị trí 10 m, cây tiếp theo ở vị trí 20 m, rồi 30 m, ...

Yêu cầu

Hãy viết chương trình tính tổng số cây cần trồng để phủ xanh toàn bộ tuyến phố đó.

Dữ liệu vào

Nhập vào từ luồng nhập/xuất chuẩn gồm:

• Một số nguyên dương duy nhất là số x (1 ≤ x ≤ 10^9) - chiều dài của tuyến đường.

Dữ liệu ra

Xuất ra luồng nhập/xuất chuẩn gồm:

• Một số nguyên duy nhất là tổng số cây cần trồng.

Ví dụ

Input

12

Output

1200

Subtasks

• Subtask 1 (30% số điểm): x ≤ 10.
• Subtask 2 (70% số điểm): Không có ràng buộc gì thêm.

Phân số lớn nhất nhưng nhỏ hơn 1

Đề bài

Trong một giờ ra chơi, hai bạn nhỏ An và Bình rủ nhau chơi một trò chơi với các phân số. Mỗi bạn lần lượt nghĩ ra và viết lên bảng những phân số dạng a_i / b_i, trong đó a_i, b_i đều là các số nguyên dương. Chẳng mấy chốc, trên bảng đã có tất cả n phân số để hai bạn cùng quan sát và so sánh.

An đưa ra một thử thách cho Bình: trong tất cả các phân số đã viết, hãy tìm phân số có giá trị lớn nhất nhưng vẫn nhỏ hơn 1. Bình thấy đây là một bài toán khá thú vị nhưng vì số lượng phân số quá nhiều nên Bình tỏ ra rất khó khăn để giải.

Hãy viết chương trình tính giúp Bình thực hiện thử thách.

Dữ liệu vào

Dữ liệu vào từ luồng nhập chuẩn gồm:

• Dòng đầu tiên chứa số nguyên dương n (1 <= n <= 10^4) — số phân số mà An và Bình viết lên bảng.
• Trong n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương a_i, b_i (1 <= a_i, b_i <= 10^6) — mô tả phân số a_i / b_i.

Dữ liệu ra

In ra luồng xuất chuẩn:

• Nếu tồn tại đáp án, hãy in phân số có giá trị lớn nhất nhưng vẫn nhỏ hơn 1 theo dạng a/b.
• Phân số phải được đưa về dạng tối giản trước khi in.
• Nếu không tồn tại phân số nào nhỏ hơn 1, in ra -1.

Ví dụ 1

Input

5
1 2
3 2
24 30
6 6
7 10

Output

4/5

Giải thích

Các phân số nhỏ hơn 1 là:

• 1/2
• 24/30
• 7/10

Trong đó 24/30 có giá trị lớn nhất. Rút gọn 24/30 ta được 4/5.

Ví dụ 2

Input

2
3 2
67 67

Output

-1

Giải thích

• 3/2 lớn hơn 1
• 67/67 bằng 1

Vì không có phân số nào nhỏ hơn 1, nên kết quả là -1.

Gợi ý

Để so sánh hai phân số a/b và c/d, không nên đổi sang số thực. Ta có thể so sánh bằng phép nhân chéo:

• a/b > c/d khi và chỉ khi a * d > c * b

Mua sắm

Để chuẩn bị cho buổi tổng kết cuối năm, cô giáo cần mua một số món quà để vinh danh học sinh có thành tích cao. Tại cửa hàng, cô giáo nhận thấy có N phần quà phù hợp để tặng học sinh, trong đó phần quà thứ i (1 ≤ i ≤ N) có giá c_i đồng.

Vì cô giáo muốn nhiều bạn có quà nhất có thể nên cần mua nhiều phần quà nhất. Tuy nhiên cô giáo chỉ có số tiền là S đồng nên tổng giá của các phần quà cô giáo mua không được vượt quá S.

Yêu cầu

Hãy xác định số phần quà lớn nhất mà cô giáo có thể mua.

Dữ liệu vào

Nhập vào từ luồng nhập/xuất chuẩn gồm:

• Dòng đầu tiên chứa hai số nguyên dương N, S
  (1 ≤ N ≤ 3 × 10^5; 1 ≤ S ≤ 10^18)
  là số phần quà và số tiền của cô giáo.

• Dòng thứ hai chứa N số nguyên dương
  c₁, c₂, ..., c_N (1 ≤ c_i ≤ 10^9)
  là giá tiền của các phần quà.

Dữ liệu ra

Xuất ra luồng nhập/xuất chuẩn gồm:

• Một số nguyên duy nhất là số phần quà nhiều nhất mà cô giáo có thể mua được.

Ví dụ

Input

6 20
8 5 3 10 2 6

Output

4

Giải thích

Cô giáo mua các phần có chỉ số 2, 3, 5, 6.

Subtasks

• Subtask 1 (40% số điểm): N ≤ 20.
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Bài 4. Lấy nước

Trong một buổi học ngoại khóa, cô giáo đưa bốn bạn An, Bình, Cúc và Dũng đến tham quan một chiếc giếng nhỏ ở gần trường. Để bài học trở nên thú vị hơn, cô nghĩ ra một trò chơi quan sát việc lấy nước của các bạn trong nhiều ngày liên tiếp. Theo quy ước của cô giáo:

• Bạn An sẽ đến giếng lấy nước mỗi a ngày một lần, tức là bạn sẽ đến giếng lấy nước vào các ngày a, 2 × a, 3 × a, ...
• Bạn Bình sẽ đến giếng lấy nước mỗi b ngày một lần, tức là bạn sẽ đến giếng lấy nước vào các ngày b, 2 × b, 3 × b, ...
• Bạn Cúc sẽ đến giếng lấy nước mỗi c ngày một lần, tức là bạn sẽ đến giếng lấy nước vào các ngày c, 2 × c, 3 × c, ...
• Bạn Dũng sẽ đến giếng lấy nước mỗi d ngày một lần, tức là bạn sẽ đến giếng lấy nước vào các ngày d, 2 × d, 3 × d, ...

Mỗi ngày, cô giáo quan sát thấy chiếc giếng luôn có sẵn 12 lít nước để chia cho các bạn đến lấy trong ngày hôm đó. Nếu chỉ có một bạn đến, bạn đó sẽ lấy 12 lít nước; nếu có hai bạn đến, mỗi bạn sẽ lấy 6 lít nước; nếu có ba bạn đến, mỗi bạn sẽ lấy 4 lít nước; nếu cả bốn bạn cùng đến, mỗi bạn sẽ lấy 3 lít nước.

Nói cách khác, lượng nước sẽ được chia đều cho các bạn đến lấy nước vào ngày hôm đó.

Cô giáo muốn ghi lại kết quả để xem trong một khoảng thời gian dài, mỗi bạn đã lấy được bao nhiêu nước. Vì số ngày quan sát có thể rất lớn, cô nhờ em viết chương trình giúp tính toán.

Yêu cầu

Sau khi quan sát m ngày, cô giáo đã đánh mất ghi chú về tổng lượng nước mà mỗi bạn đã lấy. Hãy giúp cô giáo tính toán, trong m ngày đầu tiên, mỗi bạn An, Bình, Cúc, Dũng đã lấy bao nhiêu lít nước.

Dữ liệu vào

Nhập vào từ luồng nhập/xuất chuẩn gồm:

• Một dòng duy nhất chứa năm số nguyên a, b, c, d, m (1 ≤ a, b, c, d ≤ m; 1 ≤ m ≤ 10^15)
  
  • tần suất lấy nước của các bạn An, Bình, Cúc, Dũng
  • và số ngày quan sát của cô giáo.

Dữ liệu ra

Xuất ra luồng nhập/xuất chuẩn gồm:

• Bốn số nguyên, lần lượt là số lít nước mà An, Bình, Cúc, Dũng lấy.

Ví dụ

Input
2 1 3 4 10

Output
24 72 16 8

Giải thích

Ta xét từng ngày từ ngày 1 đến 10:

• Vào ngày 1, chỉ có Bình đến lấy nước và bạn lấy được 12 lít nước.
• Vào ngày 2, An và Bình cùng đến lấy nước nên mỗi bạn lấy được 6 lít nước.
• Vào ngày 3, Bình và Cúc cùng đến lấy nước nên mỗi bạn lấy được 6 lít nước.
• Vào ngày 4, An, Bình và Dũng cùng đến lấy nước nên mỗi bạn lấy được 4 lít nước.
• Vào ngày 5, chỉ có Bình đến lấy nước và bạn lấy được 12 lít nước.
• Vào ngày 6, An, Bình và Cúc cùng đến lấy nước nên mỗi bạn lấy được 4 lít nước.
• Vào ngày 7, chỉ có Bình đến lấy nước và bạn lấy được 12 lít nước.
• Vào ngày 8, An, Bình và Dũng cùng đến lấy nước nên mỗi bạn lấy được 4 lít nước.
• Vào ngày 9, Bình và Cúc cùng đến lấy nước nên mỗi bạn lấy được 6 lít nước.
• Vào ngày 10, An và Bình cùng đến lấy nước nên mỗi bạn lấy được 6 lít nước.

Cộng lại:

• An đã lấy 6 + 4 + 4 + 4 + 6 = 24 lít nước.
• Bình đã lấy 12 + 6 + 6 + 4 + 12 + 4 + 12 + 4 + 6 + 6 = 72 lít nước.
• Cúc đã lấy 6 + 4 + 6 = 16 lít nước.
• Dũng đã lấy 4 + 4 = 8 lít nước.

Subtasks

• Subtask 1 (40% số điểm): m ≤ 1000.
• Subtask 2 (40% số điểm): a = b = c = d.
• Subtask 3 (20% số điểm): Không có ràng buộc gì thêm.