Subtask 1

Dùng thuật toán BFS.

Subtask 2

Nhận xét là giá trị ~a~ đủ nhỏ. Nhận thấy là khi ta đi đến được tầng ~F~, ta có thể đi đến tất cả các tầng có dạng ~(F \bmod a) + k \times a~ (~k \ge 0~). Ta sẽ nghĩ đến ý tưởng như sau: với mọi ~r~ thoả mãn ~0 \le r < a~, ta sẽ tìm tầng ~F~ nhỏ nhất có thể đi đến được từ tầng ~1~ sao cho ~F \bmod a = r~, gọi nó là ~h_r~.

Ta dựng đồ thị: với mọi đỉnh ~r~ ta nối cạnh đến ~(r + b) \bmod a~ với trọng số ~b~, nối cạnh đến ~(r + c) \bmod a~ với trọng số ~c~. Khi đó ~h_r~ là đường đi ngắn nhất từ đỉnh ~1 \bmod a~ đến đỉnh ~r~. Kết quả bài toán sẽ là: ~\sum_{0 \le r < a} \max \left(0, \left \lfloor \frac{n - h_r}{a} + 1 \right \rfloor \right)~