Shobon ตัดสินใจใช้ AI เชิงสร้างสรรค์ (generative AI) เพื่อช่วยพัฒนาโปรเจกต์ซอฟต์แวร์ โปรเจกต์นี้ประกอบด้วยงาน $N$ งาน แต่ละงาน $i$ ($i = 1, 2, \dots, N$) มีปริมาณงานในการเขียนโค้ดที่กำหนดไว้ล่วงหน้าคือ $A_i$ และความซับซ้อนคือ $B_i$

Shobon สามารถดำเนินการงานเหล่านี้ในลำดับใดก็ได้ อย่างไรก็ตาม เขาไม่สามารถทำงานมากกว่าหนึ่งงานในเวลาเดียวกันได้

แต่ละงาน $i$ ($i = 1, 2, \dots, N$) สามารถทำให้เสร็จสมบูรณ์ได้ด้วยวิธีใดวิธีหนึ่งจากสองวิธีต่อไปนี้:

• เขียนโค้ดทำงานนั้นด้วยตนเอง Shobon เขียนโค้ดด้วยตัวเอง ซึ่งใช้เวลา $A_i$ หน่วยเวลา
• ใช้ AI เชิงสร้างสรรค์ เพื่อให้ AI สร้างโค้ดที่ถูกต้อง Shobon ต้องอธิบายงานปัจจุบันและงานทั้งหมดที่ทำเสร็จไปแล้วก่อนหน้านี้ให้ AI เข้าใจ ให้ $S$ เป็นผลรวมของความซับซ้อนของงานทั้งหมดที่ทำเสร็จไปแล้วก่อนหน้านี้ การเตรียมคำอธิบายนี้ใช้เวลา $S + B_i$ หน่วยเวลา จากนั้น AI จะทำการเขียนโค้ดให้เสร็จสิ้นในทันที จึงไม่จำเป็นต้องใช้เวลาในการเขียนโค้ดเพิ่มเติม ดังนั้น การทำงานนี้ให้เสร็จโดยใช้ AI จึงใช้เวลารวมทั้งสิ้น $S + B_i$ หน่วยเวลา

ไม่ว่าจะใช้วิธีใดก็ตาม เมื่อทำงาน $i$ เสร็จแล้ว ความซับซ้อน $B_i$ ของงานนั้นจะถูกรวมเข้าไปในค่าของ $S$ ในอนาคตเมื่อใช้ AI เชิงสร้างสรรค์

จงหาเวลารวมน้อยที่สุดที่ต้องใช้ในการทำงานทั้งหมดให้เสร็จสมบูรณ์

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยสามบรรทัดในรูปแบบต่อไปนี้

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \end{aligned} $$

ในบรรทัดแรกจะกำหนดจำนวนงาน $N$ ($1 \le N \le 2 \times 10^5$) บรรทัดที่สองประกอบด้วยจำนวนเต็ม $N$ จำนวน คือ $A_1, A_2, \dots, A_N$ แต่ละจำนวนมีค่าระหว่าง $1$ ถึง $10^9$ (รวมขอบเขต) แทนปริมาณงานในการเขียนโค้ดของงานทั้ง $N$ งาน บรรทัดที่สามประกอบด้วยจำนวนเต็ม $N$ จำนวน คือ $B_1, B_2, \dots, B_N$ แต่ละจำนวนมีค่าระหว่าง $1$ ถึง $10^8$ (รวมขอบเขต) แทนความซับซ้อนของงานทั้ง $N$ งาน

ข้อมูลส่งออก

แสดงผลในบรรทัดเดียวเป็นเวลารวมน้อยที่สุดที่ต้องใช้ในการทำงานทั้งหมดให้เสร็จสมบูรณ์

ตัวอย่าง

ข้อมูลนำเข้า 1

3
10 6 10
5 2 4

ข้อมูลส่งออก 1

18

ข้อมูลนำเข้า 2

1
4
10

ข้อมูลส่งออก 2

4

ข้อมูลนำเข้า 3

5
100 100 100 100 100
5 1 4 2 3

ข้อมูลส่งออก 3

35

ข้อมูลนำเข้า 4

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

ข้อมูลส่งออก 4

118

หมายเหตุ

สำหรับข้อมูลนำเข้าตัวอย่างที่ 1 พิจารณาการใช้ AI เชิงสร้างสรรค์สำหรับงานที่ $2$ และ $3$ ตามลำดับนี้ แล้วจึงเขียนโค้ดทำงานที่ $1$ ด้วยตนเอง

• เมื่อเริ่มงานที่ $2$ ยังไม่มีงานใดทำเสร็จเลย งานนี้ใช้เวลา $0 + B_2 = 2$ หน่วยเวลา
• เมื่อเริ่มงานที่ $3$ งานที่ $2$ ได้ทำเสร็จไปแล้ว งานนี้ใช้เวลา $B_2 + B_3 = 2 + 4 = 6$ หน่วยเวลา
• สุดท้าย การเขียนโค้ดทำงานที่ $1$ ด้วยตนเองใช้เวลา $A_1 = 10$ หน่วยเวลา

ดังนั้น งานทั้งหมดสามารถทำเสร็จได้ในเวลา $2 + 6 + 10 = 18$ หน่วยเวลา ซึ่งเป็นค่าน้อยที่สุดที่เป็นไปได้